记录编号	454611	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.465 s
提交时间	2017-09-29 10:36:07	内存使用	16.52 MiB

/*就是50到100那个优化开始一直不是很懂，现在也只是朦朦胧胧的，大概是改变了一下求num的顺序，
50的是对于每一个i，一直往前跳，跳到符合位置，而对于100的，第一个i跳完之后，其余的i就是
在上一个i跳到的位置的周围跳，而不需要每次都从头跳*/
/*其实就是先找到第一个i小于等于1/2的位置，对于其他的点像普通求next一样求出他们的最大前缀
只不过相当于多了个限制，就是长度必须小于1/2，于是当长度大于1/2是需要往前找*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int ma=1000005;
ll next[ma],num[ma];
int n;
char s[ma];
void get_next(char *s){
	int len=strlen(s);next[0]=num[0]=0;
	for(int i=1;i<len;i++){
		int k=next[i-1];
		while(k&&s[k]!=s[i])k=next[k-1];
		num[i]=0;
		if(s[k]==s[i])next[i]=k+1,num[i]=num[k]+1;
		else next[i]=0;
	}
}
void work(char *s){
	get_next(s);
	int l=strlen(s);
	ll ans=1;
	int x=0;
	for(int i=1;i<l;i++){
		while(x&&s[x]!=s[i])x=next[x-1];
		if(s[x]==s[i])x++; 
		while(x<<1>i+1&&x)x=next[x-1];
		if(x)
		ans*=(2+num[x-1]),ans%=mod;
	}//cout<<endl;
	cout<<ans<<endl;
}
int main()
{
	freopen("zoo.in","r",stdin);freopen("zoo.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		work(s);
	}
	return 0;
}