// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

const int MOD=;

int n, nxt[], num[];

char s1[];

long long ans;

void kmp()

{

    ans=;

    nxt[]=-; num[]=;

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

    {

        for(j=nxt[i-]; j>= && s1[i]!=s1[j+]; j=nxt[j]);

        j++; nxt[i]=j;

        num[i]=num[j]+;

    }

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

    {

        for(; j>= && s1[i]!=s1[j+]; j=nxt[j]);

        j++;  //nxt[i]=j;

        for(;(j<<)>i;j=nxt[j]);

        ans*=num[j]+;ans%=MOD;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",s1+);

        n=strlen(s1+)+;

        kmp();

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

    }

    return ;

}