记录编号	381061	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]动物园	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.579 s
提交时间	2017-03-10 19:57:01	内存使用	16.50 MiB

#include <cstdio>
#include <cstring>
#define file(x) "zoo."#x
typedef long long ll;
const int L = 1e6 + 1;
const ll M = 1e9 + 7;
char s[L];
ll nxt[L], num[L];
ll solve() {
	memset(nxt, 0, sizeof(nxt));
	memset(num, 0, sizeof(num));
	int n = strlen(s + 1);
	ll res = 1;
	int p = 0, p2 = 0;
	num[1] = 1;
	for (int i = 2; i <= n; i++) {
		while (p && s[p + 1] != s[i]) p = nxt[p];
		if (s[p + 1] == s[i]) p++;
		nxt[i] = p;
		num[i] = num[p] + 1;
		while (p2 && s[p2  + 1] != s[i]) p2 = nxt[p2];
		if (s[p2 + 1] == s[i]) p2++;
		while (p2*2 > i) p2 = nxt[p2];
		res = (res*(num[p2] + 1))%M;
	}
	return res;
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%s", s + 1), printf("%lld\n", solve());
}