2020 Multi-University Training Contest 1

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
char s[maxn];
int pos[maxn];
int solve(){
    scs(s+1); int len=strlen(s+1);
    int cur=0,ans=0,pow=1,pre=1;
    rep(i,1,len+1){
        pos[++cur]=i;
        while(cur>pre&&s[i]>s[i-(pos[cur]-pos[cur-1])]) cur--;
        while(cur>pre&&s[i]<s[i-(pos[pre+1]-pos[pre])]) pre++;
        // 其实核心就这两句qwq
        // 首先是每次都要处理的 到每一位都需要更新之前的状态
        // 有点难讲qwq 通过举例子来吧 比如aabaaab
        // 处理到第一个b时 减到前面连续小的第一个 当前答案为1
        // 处理到第二个b时 通过每次跳pos[cur]-pos[cur-1]来判断是否还在连续的状态
        ans+=1ll*pow*pos[cur]%mod;
        if(ans>=mod) ans-=mod;
        pow=1112ll*pow%mod;
    } return pf("%d\n",ans);
}
int main(){
    int _; sc(_); while(_--) solve();
}