#include<cstdio>

 #include<cstring>

 using namespace std;

 char s[];

 int nxt[],num[],n;

 long long ans;

 void doit(char *s){

     int n=strlen(s);

     nxt[]=-;

     nxt[]=;

     num[]=;

     num[]=;ans=;

     for(int i=,j=;i<n;i++){

         while(j>=&&s[i]!=s[j])j=nxt[j];

         nxt[i+]=++j;

         num[i+]=num[j]+;

     }

     for(int i=,j=;i<n;i++){

         while(j>=&&s[i]!=s[j])j=nxt[j];

         j++;

         while((j<<)>(i+))j=nxt[j];

         ans=(ans*((long long)num[j]+))%;

     }

     printf("%lld\n",ans);

 }

 int main(){

     scanf("%d",&n);

     while(n--){

         scanf("%s",s);

         doit(s);

     }

 }