Submission

[PPPPPPPPPPP]

Score: 100

User: chawinkn

Problemset: A.Six Zero

Language: cpp

Time: 0.029 second

Submitted On: 2025-04-04 18:17:17

#include <bits/stdc++.h>
using namespace std;

const int M=1e9+7;

// int dp[1000009][3];

void solve() {
	string s;
	cin >> s;
	int n=s.length();
	// memset(dp, 0, sizeof(dp));
	int dp[2][3]={0};
	for (int i = 1; i <= n; i++) {
		memset(dp[i%2], 0, sizeof(dp[i%2]));
		dp[i%2][0] += (s[i-1] == '6'), dp[i%2][0] %= M; // 6
		if (s[i-1] == '0') {
			dp[i%2][1] += dp[(i-1)%2][0], dp[i%2][1] %= M; // 60
			dp[i%2][2] += dp[(i-1)%2][1], dp[i%2][2] %= M; // 600
		}
		dp[i%2][0] += dp[(i-1)%2][0], dp[i%2][0] %= M;
		dp[i%2][1] += dp[(i-1)%2][1], dp[i%2][1] %= M;
		dp[i%2][2] += dp[(i-1)%2][2], dp[i%2][2] %= M;
	}
	cout << dp[n%2][2] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}