记录编号	164104	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2015-05-28 13:52:25	内存使用	8.90 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=1000010;
const int MOD=1000000007;
int N;
char S[SIZEN];
int nxt[SIZEN],cnt[SIZEN];
void work(void){
	cnt[1]=1;
	for(int i=2;i<=N;i++){
		int j=nxt[i-1];
		while(j&&S[j+1]!=S[i]) j=nxt[j];
		if(S[j+1]==S[i]) j++;
		nxt[i]=j;
		cnt[i]=cnt[j]+1;
	}
	int ans=1;
	int j=0;
	for(int i=2;i<=N;i++){
		while(j&&S[j+1]!=S[i]) j=nxt[j];
		if(S[j+1]==S[i]) j++;
		while(j*2>i) j=nxt[j];
		ans=(1ll*ans*(cnt[j]+1))%MOD;
	}
	printf("%d\n",ans);
}
void read(void){
	scanf("%s",S+1);
	N=strlen(S+1);
}
int main(){
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}