首先求出fail数组，如果没有不重叠的限制的话，我们可以在求fail的时候递推出个数cnt[i]=cnt[fail[i]]+1（这个cnt是算上自己本身==自己本身的）
然后如果是要求不重叠的话，就是相当于一直跳fail，直到找到了一个长度不超过一半的fail，然后num[i]就是它
但如果直接暴力跳肯定是不行的
其实它跟求fail的时候是一样的，只要每次不重置那个指针，就把它当成在求fail一样往后匹配这一位，匹配完这一位再跳回到一半以下，就可以保证复杂度
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long int
using namespace std; const int M=1e9+,maxn=; char s[maxn];
int fail[maxn],fulcnt[maxn];
int len;
ll ans=; void getfail(){
int i,j,k;
fulcnt[]=;
for(i=,j=,k=;i<=len;i++){
while(j && s[j+]!=s[i]) j=fail[j];
while(k && s[k+]!=s[i]) k=fail[k];
if(s[j+]==s[i]) j++;
if(s[k+]==s[i]) k++;
fail[i]=j;
fulcnt[i]=fulcnt[j]+;
while(k&&k>i/) k=fail[k];
ans=(ans*(fulcnt[k]+))%M;
}
} int main(){
int t;
// freopen("testdata.in","r",stdin);
scanf("%d",&t);
for(;t;t--){
ans=;
scanf("%s",s+);
len=strlen(s+);
memset(fail,,sizeof(fail));
memset(fulcnt,,sizeof(fulcnt));
getfail();
printf("%lld\n",ans);
}
}