记录编号	114819	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.474 s
提交时间	2014-08-01 20:06:29	内存使用	12.69 MiB

#include <cstdio>
#include <cctype>
using namespace std;
FILE *in = fopen("zoo.in","r");
FILE *out = fopen("zoo.out","w");
const int MOD = 1000000007, MAXL = 1000003;
char P[MAXL];
int num[MAXL],next[MAXL],lnext[MAXL];
void work()
{
	long long ans = 1;
	int ch,L=0,i,j,t;
	ch = fgetc(in);
	while(!isalpha(ch))
		ch = fgetc(in);
	while(isalpha(ch)) {
		P[++L]=ch;
		num[L]=next[L]=lnext[L]=0;
		ch = fgetc(in);
	}
	for(i=1;i<L;++i)
	{
		j=i;
		while(j>0) {
			j=next[j];
			if(P[i+1]==P[j+1]) {
				lnext[i+1]=next[i+1]=j+1; //getnext
				break;
			}
		}
		if((j<<1)>i-1) {
			j = lnext[i];
			if((j<<1)>i-1) j = next[j];
			while(j>0) {
				if(P[i+1]==P[j+1]) {
					lnext[i+1]=j+1;
					break;
				}
				j=next[j];
			}
			if(!j)lnext[i+1]=1;
		}
	}
	for(i=2;i<=L;++i)
	{
		t=i>>1;
		if(!next[i])continue;
		num[i] = num[next[i]]+1;
		j=lnext[i];
		if(j)ans = ans*(num[j]+2)%MOD;
	}
	fprintf(out,"%d\n",ans);
}

int main()
{
	int n;
	fscanf(in, "%d",&n);
	while(n--)
		work();
	return 0;
}