记录编号	407947	评测结果	AAAAAAAAAA
题目名称	1686.[NOI 2014]动物园	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	1.514 s
提交时间	2017-05-23 14:06:41	内存使用	88.98 MiB

#include <cstring>
#include <cstdio>

#define MAXLOG 20
#define MAXN 1000010
#define MOD 1000000007
#define ll long long

char str[MAXN];
int next[MAXN], N;

int par[MAXLOG][MAXN], dep[MAXN];
int log[MAXN];

int main() {
	freopen("zoo.in", "rt", stdin);
	freopen("zoo.out", "wt", stdout);

	int i, T, k;
	for(i=2;i<MAXN;i++) log[i] = log[i>>1] + 1;

	scanf("%d", &T); while(T--) {
		scanf("%s", str); N = strlen(str);
		//get next
		next[0] = next[1] = 0; dep[1] = 1;
		for(i=1,k=0;i<N;i++) {
			while(k && str[i] != str[k]) k = next[k];
			if(str[i] == str[k]) k++;
			
			next[i+1] = k;
			par[0][i+1] = k; dep[i+1] = dep[k] + 1;
		}
		
		//make tree
		for(k=1;(1<<k)<=N;k++) {
			for(i=0;i<=N;i++) par[k][i] = par[k-1][par[k-1][i]];
		}
		
		//repeat
		int Ans = 1, x, num, maxlen;
		for(i=1;i<=N;i++) if(next[i]) {
			maxlen = i/2; x = i;
			
			for(k=log[dep[x]];k>=0;k--) {
				if(par[k][x] > maxlen) x = par[k][x];
			}
			x = par[0][x];
			
			Ans = ((ll)Ans * (dep[x] + 1)) % MOD;
		}
		printf("%d\n", Ans);
	}
}