题目链接： http://uoj.ac/problem/5

题意： 中文题目

解法：
如果num数组记载的前后缀允许重叠，是可以在递推next数组时顺路O(L)求出来的，这一步还算比较简单。
重点在于如何通过这个允许重叠的num数组求出不允许重叠时对应的num值。方法是让整个串再自己匹配自己一次，不过每次匹配时，如果j+1>(i+1)/2，即发现有重叠时，也要沿着next走。如果匹配成功，即str[i]==str[j]，则说明i的num值应该是num[j]的值（因为也是这样递推算过来的），相乘即可；若匹配不成功，说明此时i的num值为0，答案要乘上1所以可以忽略。

//NOIP 2014

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000010;
const int mod = 1000000007;
char s[maxn];
int fail[maxn], nxt[maxn];
long long ans;

int main()
{
    int t; scanf("%d", &t);
    while(t--){
        ans = 1;
        scanf("%s", s+1);
        int len = strlen(s+1);
        int j = 0;
        memset(fail, 0, sizeof(fail));
        memset(nxt, 0, sizeof(nxt));
        nxt[1] = 1;
        for(int i = 2; i <= len; i++){
            while(s[j+1] != s[i] && j > 0) j = fail[j];
            if(s[j+1] == s[i]) j++;
            fail[i] = j;
            nxt[i] = nxt[j]+1;
        }
        j = 0;
        for(int i = 2; i <= len; i++){
            while(s[j+1]!=s[i]&&j>0) j = fail[j];
            if(s[j+1]==s[i]) j++;
            while((j<<1)>i&&j>0) j = fail[j];
            ans = (ans*(nxt[j]+1))%mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}