#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int const maxn=;

ll ans,mod=1e9+;

int n,nxt[maxn],num[maxn];

char a[maxn];

int rd()

{

    int ret=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return ret*f;

}

int main()

{

    n=rd();

    while(n--)

    {

//        scanf("%s",&a+1);

        cin>>a+;

        int l=strlen(a+);

        memset(nxt,,sizeof nxt);

        memset(num,,sizeof num);

        ans=; nxt[]=; num[]=;//

        int nw=,nw2=;

        for(int i=;i<=l;i++)

        {

//            int nw=nxt[i-1];

            while(a[i]!=a[nw+]&&nw)nw=nxt[nw];

//            if(nw==-1&&a[1]==a[i])nxt[i]=1;

//            else

//            nxt[i]=nw+1;

//            nw=nxt[i];

            if(a[i]==a[nw+])nw++;

            nxt[i]=nw;

            num[i]=num[nw]+;

//            printf("num[%d]=%d\n",i,num[i]);

//            printf("nxt[%d]=%d\n",i,nxt[i]);

            while(a[i]!=a[nw2+]&&nw2)nw2=nxt[nw2];

            if(a[i]==a[nw2+])nw2++;

            while(nw2*>i)

            {

//                if(nw*2<=i)

//                {

//                    num[i]=num[nw]+1;break;

//                }

//                cout<<nw<<endl;

                nw2=nxt[nw2];

            }

//            printf("i:%d num=%d\n",i,num[i]);

            (ans*=(num[nw2]+))%=mod;

        }

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

    }

    return ;

}