555

#include<bits/stdc++.h>
using namespace std;
int n,nxt[1000005],num[1000005];
string s;
void get_next(){
    nxt[0]=nxt[1]=0;
    for(int i=1;i<s.size();i++){
        int j=nxt[i];
        while(j && s[i]!=s[j])
            j=nxt[j];
        if(s[i]==s[j])
            nxt[i+1]=j+1;
        else
            nxt[i+1]=0;
    }
}
long long get_num(){
    num[0]=0,num[1]=0;
    long long ans=1;
    for(int i=2;i<=s.size();i++){
        int j=nxt[i];
        while(j){
            if(2*j<=i)
                ++num[i];
            j=nxt[j];
        }
        ans*=(num[i]+1);
        ans%=1000000007;
    }
    return ans;
}
int main(){
    cin>>n;
    while(n--){
        cin>>s;
        memset(nxt,0,sizeof(nxt));
        memset(num,0,sizeof(num));
        get_next();
        cout<<get_num()<<"\n";
    }
    return 0;
}

T了

实在不会优化了QwQ

把KMP都给忘光了