Submission

Score: 100

User: hmmm

Problemset: A.Six Zero

Language: cpp

Time: 0.041 second

Submitted On: 2025-09-18 11:12:35

#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
const int MOD=1e9+7;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n=s.size();
        ll dp[5][n+5],ans=0;
        memset(dp,0,sizeof dp);
        for(int i=0;i<3;i++){
            ll cnt=0;
            for(int j=0;j<n;j++){
                if(i==0){
                    if(s[j]=='6'){
                        dp[i+1][j+1]+=1;
                    }
                }
                else{
                    cnt+=dp[i][j];
                    cnt%=MOD;
                    if(s[j]=='0'){
                        dp[i+1][j+1]+=cnt;
                    }
                }
            }
        }
        // for(int i=0;i<=3;i++){
        //     for(int j=0;j<n;j++){
        //         cout << dp[i][j] << ' ';
        //     }
        //     cout << "\n";
        // }
        for(int i=0;i<=n;i++){
            ans+=dp[3][i];
            ans%=MOD;
        }
        cout << ans << "\n";
    }
}