Submission

Score: 100

User: mydKN

Problemset: A.Six Zero

Language: cpp

Time: 0.054 second

Submitted On: 2025-01-05 15:52:46

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int q;

/*
int ncr(int n, int r){
	int sum = 1;
	for(int i=1;i<=r;++i){
		sum = (sum * (n - r + i) / i) % MOD;
	}
	return sum;
}
*/

int mod_exp(int base, int exp){
	int res = 1;
	while(exp > 0){
		if(exp % 2 == 1){
			res = (1LL * res * base) % MOD;
		}
		base = (1LL * base * base) % MOD;
		exp /= 2;
	}
	return res;
}

int mod_inverse(int x){
	return mod_exp(x, MOD - 2);
}

int ncr(int n, int r){
	if(r > n) return 0;
	int numerator = 1, denominator = 1;
	for(int i=0;i<r;++i){
		numerator = (1LL * numerator * (n - i)) % MOD;
		denominator = (1LL * denominator * (i + 1)) % MOD;
	}
	return (1LL * numerator * mod_inverse(denominator)) % MOD;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> q;
	while(q--){
		string str;
		cin >> str;
		vector<int> vec;
		for(int i=0;str[i]!='\0';++i){
			if(str[i] == '6') vec.emplace_back(i);
		}
		int cnt = 0;
		for(int i=0;i<vec.size();++i){
			cnt = (cnt + ncr(str.length()-vec[i]-(vec.size()-i), 2)) % MOD;
		}
		cout << cnt << "\n";
	}
}