记录编号	291053	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.340 s
提交时间	2016-08-07 10:05:51	内存使用	8.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
#define mod 1000000007
using namespace std;
char ch[maxn];
int n,next[maxn],num[maxn],ans,k;
void getnext(){
	num[1]=1;
	for(int i=2;i<=n;i++){
		int j=next[i-1];
		while(j&&ch[j+1]!=ch[i])j=next[j];
		if(ch[j+1]==ch[i])j++;
		next[i]=j;
		num[i]=num[j]+1;
			/*
		如果暂时不考虑重叠的子串个数用num[i]表示，利用next表的性质,一定有num[i]=num[next[i]]+1;
		num[next[i]]表示next[i]之前的能够满足性质的子串个数，而i和next[i]是完全重合的一段，
		所以num[i]=num[next[i]]+1(i和next[i]也满足性质，所以+1) 目前都不考虑重叠的情况，
		如果能重复的话那么任何串自己和自己就可以算是一组，所以边界条件num[1]=1,记得是考虑重复！
		在求next的时候顺便求出num来就好了 
		*/
	}
}
int main(){
	freopen("zoo.in","r",stdin);freopen("zoo.out","w",stdout);
	int T;cin>>T;
	while(T--){
		scanf("%s",ch+1);
		n=strlen(ch+1);
		getnext();
		ans=1,k=0;
		for(int i=2;i<=n;i++){
			while(k&&ch[k+1]!=ch[i])k=next[k];//一直跳 
			if(ch[k+1]==ch[i])k++;
			while(k*2>i)k=next[k];
			ans=(1LL*ans*(num[k]+1))%mod;
		}
		/*
		现在考虑不能重叠那么j应该满足j<=i/2 所以在第二次扫过的时候只要j不满足条件，j=next[j]。答案乘上cnt[j]+1就好
		第二次求的时候j跳的时候和求next是相同的，不过是j必须要小于i/2，实际上求得是小于i/2的 能和i匹配上的位置。
		*/
		printf("%d\n",ans);
	}
	return 0;
}