P2375.cpp

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

using i64 = long long;
const int N = 1e6+10;
const i64 P = 1e9+7;
int nxt[N], dep[N];

int solve() {
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;

    for (int i = 2; i <= n; i++) {
        nxt[i] = nxt[i-1];
        while (nxt[i] && s[nxt[i]+1] != s[i]) nxt[i] = nxt[nxt[i]];
        if (s[nxt[i]+1] == s[i]) nxt[i]++;
    }

    for (int i = 1; i <= n; i++) dep[i] = dep[nxt[i]] + 1;

    int j = 0;

    i64 ans = 1;
    for (int i = 1; i <= n; i++) {
        while (j && s[j+1] != s[i]) j = nxt[j];
        if (s[j+1] == s[i]) j++;
        if (j > i/2) j = nxt[j];
        ans = ans * (dep[j] + 1) % P;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) cout << solve() << '\n';
    return 0;
}