$题目描述：$

$ 设num_i表示满足以下条件的字符串T的数量：$

$ 对于字符串S的前i个字符构成的子串，T既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠。$

$ 输出\prod_{i = 1}^{L}(num{[i]}+1)对\mod = 1e^9 + 7取模的结果。$

$输入格式:$

$第一行仅包含一个正整数n，表示测试数据的组数。$

$随后n行，每行描述一组测试数据。$

$每组测试数据仅含有一个字符串S,S的定义详见题目描述。数据保证 S$

$中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。$

$输出格式:$

$包含n行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。$

$对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对\mod = 1e^9 + 7$

$取模的结果。输出文件中不应包含多余的空行。$

样例输入
3
aaaaa
ab
abcababc
样例输出
36
1
32

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<cstring>

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e6 + 1;

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