rt，这个代码逆天到自己也有点看不懂，最后靠路径压缩A的，想知道此解法的可行性，如果是错误的求Hack。正确的话我就水一篇题解

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
int T,n,ans;
string s;
queue<int>road;
int kmp[1001000],num[1001000];
int cnt[1001000];
bool vis[1001000];
int DFS(int x){
	if(vis[x])return cnt[x];
	if(x==0)return 0;
	vis[x]=1;
	cnt[x]=DFS(kmp[x-1])+1;
	return cnt[x];
}
signed main(){
	cin>>T;
	while(T--){
		cin>>s;
		int j=0,ans=1;
		n=s.size();
		num[0]=kmp[0]=cnt[0]=0;
		for(int i=1;i<n;i++){
			num[i]=0,kmp[i]=0,cnt[i]=0,vis[i]=0;
			while(j&&s[i]!=s[j])j=kmp[j-1];
			if(s[i]==s[j])j++;
			kmp[i]=j;
		}
		for(int i=n;i>0;i--)DFS(i);
		for(int i=n-1;i>=0;i--){
			int t=kmp[i];
			while(t*2>i+1){
				road.push(t);
				t=kmp[t-1];
			}
			while(!road.empty()){
				kmp[road.front()-1]=t;
				road.pop();
			}
			num[i]=(num[i]+cnt[t])%mod;
			ans=ans*(num[i]+1)%mod;
		}
		cout<<ans<<'\n';
	}
	return 0;
}