#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define N 1919810
#define p 1000000007
#define int long long
using namespace std;
int fi[N],ps[N],tot,base=131,t,n;
int a[N],b[N];
string lz;
void csh_hash(){
	fi[0]=1;
	for(int i=1;i<=1919810;i++)fi[i]=fi[i-1]*base;
}
struct string_hash{
	int h[N];
	void set(string s){
		int n=s.size();
		for(int i=0;i<n;i++)h[i]=h[i-1]*base+(s[i]-'a'+1);
	}
	int query(int l,int r){return h[r]-h[l-1]*fi[r-l+1];}
}hs;
int lcs(int x,int y,int len){
	int l=0,r=len;
	while(l<=r){
		int mid=(l+r)>>1;
		if(hs.query(x-mid+1,x)==hs.query(y-mid+1,y))l=mid+1;
		else r=mid-1; 
	}
	return r;
}
int lcp(int x,int y,int len){
	int l=0,r=n-y+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(hs.query(x,x+mid-1)==hs.query(y,y+mid-1))l=mid+1;
		else r=mid-1; 
	}
	return r;
}
signed main(){
	scanf("%lld",&t);
	csh_hash();
	while(t--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		cin>>lz;
		lz="0"+lz;
		hs.set(lz);
		n=lz.size()-1;
		for(int len=1;len<=(n>>1);len++){
			int j=len,k=len*2;
			while(k<=n){
				int l=max(k-lcs(j,k,len)+len,k);
				int r=min(k+lcp(j,k,len)-1,k+len-1);
				if(l<=r){
					b[l]++;
					b[r+1]--;
					a[l-2*len+1]++;
					a[r-2*len+2]--;
				}
				j+=len,k+=len;
			}
		}
		for(int i=1;i<=n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
		int ans=0;
		for(int i=1;i<=n-1;i++)ans=(ans+a[i+1]*b[i])%p;
		printf("%lld\n",ans);
	}
	return 0;
}

验证码when祭