Chef had an interesting dream last night. He dreamed of a new revolutionary chicken recipe. When he woke up today he tried very hard to reconstruct the ingredient list. But, he could only remember certain ingredients. To simplify the problem, the ingredient list can be represented by a string of lowercase characters 'a' - 'z'.
Chef can recall some characters of the ingredient list, all the others, he has forgotten. However, he is quite sure that the ingredient list was a palindrome.
You are given the ingredient list Chef dreamed last night. The forgotten characters are represented by a question mark ('?'). Count the number of ways Chef can replace the forgotten characters with characters 'a' - 'z' in such a way that resulting ingredient list is a palindrome.

-----Input-----
The first line of input contains a single integer T, the number of test cases. T lines follow, each containing a single non-empty string - the ingredient list as recalled by Chef. Whatever letters he couldn't recall are represented by a '?'.

-----Output-----
For each test case, output a single line containing the number of valid ways the ingredient list could be completed. Since the answers can be very large, output each answer modulo 10,000,009.

-----Example-----
Input:
5
?
??
ab?
a?c
aba

Output:
26
26
1
0
1

-----Constraints-----

1 ≤ T ≤ 20

1 ≤ sum of length of all input strings ≤ 1,000,000

Each input string contains only lowercase roman letters ('a' - 'z') or question marks.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here

 
t=int(input())
for _ in range(t):
 l = input()
 
 n= len(l)
 prod = 1
 for k in range(n//2):
  i = l[k]
  j = l[n-k-1]
  if ((i!=j) and (i!='?' and j!="?") ):
   prod=0
   break
  elif ((i==j) and (i=='?')):
   prod*=26
  prod = prod%10000009
 if n%2!=0:
  if l[n//2]=="?":
   prod*=26
 
 print(prod)

# cook your dish here

t = 0 
try:
 t = int(input())
except:
 pass
 
 


for _ in range(t):
 l = input()
 
 n= len(l)
 prod = 1
 for k in range(n//2):
  i = l[k]
  j = l[n-k-1]
  if ((i!=j) and (i!='?' and j!="?") ):
   prod=0
   break
  elif ((i==j) and (i=='?')):
   prod*=26
  prod = prod%10000009
 if n%2!=0:
  if l[n//2]=="?":
   prod*=26
 
 print(prod)
  


# cook your dish here

t = 0 
try:
 t = int(input())
except:
 pass
 
 


for _ in range(t):
 l = input()
 
 n= len(l)
 prod = 1
 for k in range(n//2):
  i = l[k]
  j = l[n-k-1]
  if ((i!=j) and (i!='?' and j!="?") ):
   prod*=0
   break
  elif ((i==j) and (i=='?')):
   prod*=26
  prod = prod%10000009
 if n%2!=0:
  if l[n//2]=="?":
   prod*=26
 
 print(prod)
  


for _ in range(int(input())):
 s=list(input())
 n=len(s)
 S, mod = 1, 10000009
 for i in range(n):
  if(s[i]=="?" and s[n-i-1]=="?"):
   S = (S*26)%mod
   s[i], s[n-i-1] = ".", "."
  elif(s[i]!="?" and s[n-i-1]!="?"):
   if s[i]!=s[n-i-1]:
    S=0
    break
 print(S%mod)
   
   


for _ in range(int(input())):
 s=list(input())
 n=len(s)
 an=1
 mod=10000009
 for i in range(n):
  if s[i]=="?" and s[n-i-1]=="?":
   an=(an*26)%mod
   s[i]="."
   s[n-i-1]="."
  elif s[i]!="?" and s[n-i-1]!="?":
   if s[i]!=s[n-i-1]:
    an=0
    break
 print(an%mod)
   
   


# cook your dish here
t=int(input())
for _ in range(t):
 s=input()
 s=[i for i in s]
 n=len(s)
 # print(n,'---')
 c=1
 mc=1
 for i in range(len(s)):
  if s[i]=='?' and s[abs(n-1-i)]=='?':
   s[abs(n-1-i)]=s[i]='a'
   
   c*=26
  
  elif s[i]!=s[abs(n-1-i)] and s[i]!='?' and s[abs(n-1-i)]!='?':
   c=0
   mc=0
   break
  c=c%10000009
 
 print(c)

from math import ceil

def isPalindrome(s,N):
 for i in range(ceil(N/2)):
  if(s[i]!=s[N-i-1] and s[i]!='?' and s[N-i-1]!='?'):
   return False
 return True

T = int(input())
ans = []
m = 10**7 + 9

for _ in range(T):
 S = input()
 N = len(S)

 if(isPalindrome(S,N)):
  count = 0
  for i in range(ceil(N/2)):
   if(S[i]=='?' and S[N-1-i]=='?'):
    count += 1
  if(count==0):
   ans.append(1)
  else:
   ans.append( ((26%m)**count)%m )
 else:
  ans.append(0)

for i in ans:
 print(i)



from math import ceil

def isPalindrome(s,N):
 for i in range(ceil(N/2)):
  if(s[i]!=s[N-i-1] and s[i]!='?' and s[N-i-1]!='?'):
   return False
 return True

T = int(input())
ans = []
m = 10**7 + 9

for _ in range(T):
 S = input()
 N = len(S)

 if(isPalindrome(S,N)):
  count = 0
  for i in range(ceil(N/2)):
   if(S[i]=='?' and S[N-1-i]=='?'):
    count += 1
  if(count==0):
   ans.append(1)
  else:
   ans.append( ((26%m)**count)%m )
 else:
  ans.append(0)

for i in ans:
 print(i)


test=int(input())
for _ in range(test):
 strText=input()
 n=len(strText)
 ans=1
 rangeCheck=n
 if(n%2==0):
  rangeCheck=rangeCheck//2
 else:
  rangeCheck=rangeCheck//2+1
  
 if(len(strText)==strText.count('?')):
  ans=(ans*(26**rangeCheck))%(10**7+9)
 else:
  for i in range(rangeCheck):
   start=strText[i]
   end=strText[n-1-i]
   if(start=='?' and end=='?'):
    ans=(ans*26)%(10**7+9)
   else:
    if(start!=end):
     if(start!='?' and end!='?'):
      ans=0
      break
 print(ans)#just code here

mod =10**7 + 9
from sys import stdin,stdout
for _ in range(int(stdin.readline())):
 s = input().strip()
 n = len(s);m = 1
 for i in range(n//2):
  #print(i,n-i-1)
  if s[i]==s[n-i-1] and s[i]=='?':
   m= (m*26)%mod
  elif s[i]!= s[n-i-1] and (s[i]=='?' or s[n-i-1]=='?')    :
   pass
  elif s[i]==s[n-i-1]:
   pass
  else:
   print(0)
   break
 else:
  if n %2 ==1 and s[n//2] =='?':
   m = (m*26)%mod
  print(m)

mod =10**7 + 9
from sys import stdin,stdout
for _ in range(int(stdin.readline())):
 s = input().strip()
 n = len(s);m = 1
 for i in range(n//2):
  #print(i,n-i-1)
  if s[i]==s[n-i-1] and s[i]=='?':
   m= (m*26)%mod
  elif s[i]!= s[n-i-1] and (s[i]=='?' or s[n-i-1]=='?')    :
   pass
  elif s[i]==s[n-i-1]:
   pass
  else:
   print(0)
   break
 else:
  if n %2 ==1 and s[n//2] =='?':
   m = (m*26)%mod
  print(m)




# cook your dish here
for _ in range(int(input())):
 s=input()
 m=10**7+9
 i=0 
 j=len(s)-1
 c=1 
 while i<=j:
  if s[i]==s[j]=='?':
   c=((c%m)*(26%m))%m 
   i+=1 
   j-=1 
  elif s[i]=='?' or s[j]=='?' or s[i]==s[j]:
   i+=1 
   j-=1 
  else:
   c=0 
   break 
 print(c)

for u in range(int(input())):
 s=input()
 i=0
 j=len(s)-1
 c=1
 m=10**7+9
 while(i<=j):
  if(s[i]==s[j]=='?'):
   c=((26%m)*(c%m))%m
   i+=1
   j-=1
  elif(s[i]=='?' or s[j]=='?' or s[i]==s[j]):
   i+=1
   j-=1
  else:
   c=0
   break
 print(c%m)


# def recur(a,st,end,ans):
#     if st<=end:
#         if a[st] == '?' and a[end] == "?":
#             ans*=26
#             return recur(a,st+1,end-1,ans)
#         if a[st]!='?' and a[end]!='?':
#             if a[st] == a[end]:
#                 return recur(a,st+1,end-1,ans)
#             return 0
#         return recur(a,st+1,end-1,ans)
#     return ans

for _ in range(int(input())):
 a = input()
 i = 0
 j = len(a)-1
 ans = 1
 mod = (10**7)+9
 while i<=j:
  if a[i] == '?' and a[j] == "?":
   ans=((ans%mod)*(26%mod))%mod
   i+=1
   j-=1
  elif a[i] == '?' or a[j] == "?" or a[i] == a[j]:
   i+=1
   j-=1
  else:
   ans = 0
   break
 print(ans)


test = int(input())
for _ in range(test):
 string=list(input())
 answer=1
 for i in range(len(string)//2):
  if string[i]=='?' and string[len(string)-i-1]=='?':
   answer = (answer*26)%10000009
  elif string[i]=='?' or string[len(string)-i-1]=='?':
   answer=(answer*1)
  elif string[i]!=string[len(string)-i-1]:
   answer=0
   break
 if len(string)%2!=0:
  if string[len(string)//2]=='?':
   answer=(answer*26)
 print(answer%10000009)

def solve():
 s=input()
 n=len(s)
 c=1
 for i in range(((n-1)//2)+1):
  if s[i] == '?' and s[n-i-1] == "?":
   c=(c*26) % 10000009
  elif s[i] == '?' or s[n-i-1] == "?":
   c=c*1
  elif s[i] != s[n-i-1]:
   c=0
   break

 print(c)
 

def __starting_point():
 t=int(input())
 while t>0:
  solve()
  t=t-1
__starting_point()

# cook your dish here
for t in range(int(input())):
 s=input()
 n=len(s)
 c,k=1,0
 for i in range(((len(s)-1)//2)+1):
  if s[i]=='?' and s[n-i-1]=='?':
   c=(c*26)%10000009
  elif s[i]=='?' or s[n-i-1]=='?':
   pass
  elif s[i]!=s[n-i-1]:
    k=1
    break
 if k==1:
  print(0)
 else:
  print(c)

mod = 10000009


def solve():
 s = input()
 n = len(s)
 c, k = 1, 0
 for i in range(((len(s) - 1) // 2) + 1):
  if s[i] == '?' and s[n - i - 1] == '?':
   c = (c * 26) % 10000009
  elif s[i] == '?' or s[n - i - 1] == '?':
   pass
  elif s[i] != s[n - i - 1]:
   k = 1
   break
 if k == 1:
  print(0)
 else:
  print(c)


def __starting_point():
 t = int(input())
 while t != 0:
  solve()
  t -= 1

__starting_point()

# cook your dish here
for t in range(int(input())):
 s=input()
 n=len(s)
 c,k=1,0
 for i in range(((len(s)-1)//2)+1):
  if s[i]=='?' and s[n-i-1]=='?':
   c=(c*26)%10000009
  elif s[i]=='?' or s[n-i-1]=='?':
   pass
  elif s[i]!=s[n-i-1]:
    k=1
    break
 if k==1:
  print(0)
 else:
  print(c)

# cook your dish here
for t in range(int(input())):
 s=input()
 n=len(s)
 c,k=1,0
 for i in range(((len(s)-1)//2)+1):
  if s[i]=='?' and s[n-i-1]=='?':
   c=(c*26)%10000009
  elif s[i]=='?' or s[n-i-1]=='?':
   pass
  elif s[i]!=s[n-i-1]:
    k=1
    break
 if k==1:
  print(0)
 else:
  print(c)