TLE #21 求卡常

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
const int Mod=998244853;
const int mod=1e9+7;
const int Base=1145141;
int n;
char a[2][N];
int len[2],pos[2][N],f[2][N];
LL Pow[N];
LL Hash[2][N];
LL getHash(int op,int l,int r){
    if(l>r) return 0;
    return (Hash[op][r]-Hash[op][l-1]*Pow[r-l+1]%Mod+Mod)%Mod;
}
LL get(int op,int x,int p){
    if(x<p) return getHash(op,1,x);
    else return (getHash(op,1,p-1)*Pow[x-p+1]%Mod+getHash(op,p+1,x+1))%Mod;
}
int check(int op1,int op2,int m1,int m2,int p1,int p2){
    int l=1,r=min(m1-1,m2-1),p=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(get(op1,mid,p1)==get(op2,mid,p2)) p=mid,l=mid+1;
        else r=mid-1;
    }
    return a[op1][p+1+(p+1>=p1&&p+1<m1)]<=a[op2][p+1+(p+1>=p2&&p+1<m2)];
}
void init(int op,int m){
    for(int i=1;i<=m;i++) Hash[op][i]=(Hash[op][i-1]*Base%Mod+(a[op][i]-'a'+1))%Mod;
    int l=0,r=m+1,p=1;
    for(int i=2;i<=m;i++){
        if(a[op][i]>a[op][i-1]){
            for(int j=i-1;j>=p;j--) pos[op][--r]=j;
            p=i;
        }
        if(a[op][i]<a[op][i-1]){
            for(int j=p;j<=i-1;j++) pos[op][++l]=j;
            p=i;
        }
    }
    for(int i=p;i<=m;i++) pos[op][++l]=i;
}
int main(){
    scanf("%d",&n);
    Pow[0]=1;
    for(int i=1;i<N;i++) Pow[i]=Pow[i-1]*Base;
    scanf("%s",a[1]+1);
    len[1]=strlen(a[1]+1)+1;
    a[1][len[1]]='.';
    init(1,len[1]);
    for(int i=1;i<=len[1];i++) f[1][i]=1;
    for(int i=2;i<=n;i++){
        scanf("%s",a[i%2]+1);
        len[i%2]=strlen(a[i%2]+1)+1;
        a[i%2][len[i%2]]='.';
        init(i%2,len[i%2]);
        LL sum=0;
        for(int j=1,k=1;j<=len[i%2];j++){
            while(k<=len[(i-1)%2]&&check((i-1)%2,i%2,len[(i-1)%2],len[i%2],pos[(i-1)%2][k],pos[i%2][j])){
                sum=(sum+f[(i-1)%2][k++])%mod;
            }
            f[i%2][j]=sum;
        }
    }
    LL ans=0;
    for(int i=1;i<=len[n%2];i++){
        ans=(ans+f[n%2][i])%mod;
    }
    printf("%lld\n",ans);
    return 0;
}