AC代码求证明

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int T;
int nxt[N];
int f[N];
char a[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while (T -- ) {
		string st;
		cin >> st;
		int n = st.size ();
		for (int i = 1; i <= n; i ++ ) a[i] = st[i - 1];
		for (int i = 2, j = 0; i <= n; i ++ ) {
			while (j > 0 && a[j + 1] != a[i]) j = nxt[j];
			if (a[j + 1] == a[i]) j ++ ;
			nxt[i] = j;
		}
		long long ans = 1;
		for (int i = 2; i <= n; i ++ ) {
			int p = nxt[i], len = 0, s = 1;
			while (p) {
				if (p <= i / 2) s ++ ;
				p = nxt[p];
				if (f[p]) {
					s += f[p];
					break;
				}
			}
			f[i] = s % mod;
			ans = ans * (s) % mod;
		}
		cout << ans << endl;
	}	
	return 0;
}