#include
#include<string.h>
using namespace std;
int main()
{
unsigned long long int test;
cin>>test;
while(test–)
{
unsigned long long int var=10000009;
char str[1000020];
cin>>str;
unsigned long long len=strlen(str);
if(len%2==0)
{
unsigned long long int flag=0;
unsigned long long mid=len/2;
unsigned long long ans=1;
for(unsigned long long i=mid-1,j=mid;(i>=0 && j<len);i–,j++)
{
if((str[i]=='?') && (str[j]=='?'))
ans=ans*26;
else if((str[i]!=str[j]) && (str[i]!='?') && (str[j]!='?'))
{
cout<<0<<"\n";
flag=1;
break;
}
}
if(flag!=1)
cout<<ans%var<<"\n";
}
else
{
unsigned long long int flag=0;
unsigned long long int mid=len/2;
unsigned long long int ans=1;
if(str[mid]=='?')
ans=ans*26;
for(unsigned long long int i=mid-1,j=mid+1;(i>=0 && j<len);i--,j++)
{
if((str[i]=='?') && (str[j]=='?'))
ans=ans*26;
else if((str[i]!=str[j]) && (str[i]!='?') && (str[j]!='?'))
{
cout<<0<<"\n";
flag=1;
break;
}
}
if(flag!=1)
cout<<ans%var<<"\n";
}
return 0;
}
}