rt，本人使用的是本题的 $O(Tnlogn)$ 的倍增写法，但是会TLE ，而且很奇怪的是只在第二个和第十个点TLE，遂求调（后来把define int long long 删了之后卡过去了，但还是不解）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=1e9+7;
char s[N];
int fail[N];
int fa[N][22];
int num[N],dep[N];
void upd(int &x,int y){x=(x*(y%MOD))%MOD;}
signed main(){
	int T;
	cin>>T;
	while(T--){
		cin>>s+1;
		int l=strlen(s+1);
		for(int i=2,j=0;i<=l;i++){
			while(j&&s[j+1]!=s[i])j=fail[j];
			if(s[j+1]==s[i])j++;
			fail[i]=j;
		}//求fail数组 
		int ans=1;
		dep[0]=0;//每个点在fail树中的深度 
		for(int i=1;i<=l;i++){
			fa[i][0]=fail[i];
			for(int k=1;k<=21;k++)fa[i][k]=fa[fa[i][k-1]][k-1]; 
			int j=i;
			for(int k=21;k>=0;k--)if(fa[j][k]>(i>>1))j=fa[j][k];//倍增 
			j=fail[j];
			upd(ans,dep[j]+1);//dep[j]==num[i] 
			dep[i]=dep[fail[i]]+1;
		}
		cout<<ans<<endl;
	}
}