RT，nlogn的倍增奇怪写法

// Problem: P2375 [NOI2014] 动物园
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2375
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define M 1000005
#define int long long
const int p=1e9+7;
int T,f[M],ans,d[M],fa[M],lf[M][35];
string s;
vector<int>road[M];
void done(string x)
{
	for(int r=1;r<x.length();r++)
	{
		int l=f[r-1];
		while(l>0&&x[r]!=x[l]) l=f[l-1];
		if(x[r]==x[l]) l++;
		f[r]=l;
	}
}
void Reset()
{
	memset(d,0,sizeof(d));
	memset(lf,0,sizeof(lf));
	memset(road,0,sizeof(road));
	ans=1;
}
void dfs(int x)
{
	for(int i=0;i<road[x].size();i++)
	{
		d[road[x][i]]=d[x]+1;
		lf[road[x][i]][0]=x;
		dfs(road[x][i]);
	}
}
void Re(int x)
{
	int D=log2(d[x]);
	for(int i=1;i<=D;i++)
	{
		lf[x][i]=lf[lf[x][i-1]][i-1];
	}
	for(int i=0;i<road[x].size();i++)
	{
		Re(road[x][i]);
	}
}
int done(int x)
{
	int now=x;
	for(int D=log2(d[x]);D>=0;D--)
	{
		if(lf[now][D]>x/2)
		{
			now=lf[now][D];
		}
	}
	return d[lf[now][0]]%p;
}
signed main()
{
	cin>>T;
	for(int i=1;i<=T;i++)
	{
		Reset();
		cin>>s;
		done(s);
		road[0].push_back(1);
		for(int i=2;i<=s.length();i++)
		{
			road[f[i-1]].push_back(i);
		}
		d[0]=1;
		dfs(0);
		Re(0);
		for(int i=1;i<=s.length();i++)
		{
			ans*=done(i);ans%=p;
			// cout<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}
/*
看懂掌声
*/