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: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	l = input()
	n = len(l)
	(a, b, c) = (0, n - 1, 1)
	while a <= b:
		if l[a] == '?' == l[b]:
			c = c * 26 % 10000009
		elif l[a] != '?' and l[b] != '?' and (l[a] != l[b]):
			c = 0
			break
		a += 1
		b -= 1
	print(c)


for _ in range(int(input())):
	s = input()
	nWays = 1
	n = len(s)
	for i in range(n // 2):
		if s[i] == '?' and s[-1 - i] == '?':
			nWays = nWays * 26 % 10000009
		elif s[i] != '?' and s[-1 - i] != '?' and (s[i] != s[-i - 1]):
			nWays = 0
			break
	if n % 2 and s[n // 2] == '?':
		nWays = nWays * 26 % (10 ** 7 + 9)
	print(nWays)


for _ in range(int(input())):
	s = input()
	N = len(s)
	ans = 1
	for i in range(N // 2 + N % 2):
		if s[i] == '?':
			if s[N - 1 - i] == '?':
				ans = ans * 26 % 10000009
		elif s[N - 1 - i] != '?' and s[N - 1 - i] != s[i]:
			ans = 0
			break
	print(ans)


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)


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()


for j in range(int(input())):
	s = input()
	l = len(s)
	ans = 1
	mod = 10000009
	for i in range((l + 1) // 2):
		if s[i] != s[l - 1 - i] and s[i] != '?' and (s[l - 1 - i] != '?'):
			ans = 0
			break
		elif s[i] == '?' and s[l - 1 - i] == '?':
			ans = ans * 26 % mod
	print(ans)


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	s = args[0]
	n = len(s)
	res = 1
	for i in range((n + 1) // 2):
		if s[i] != s[n - i - 1] and s[i] != '?' and (s[n - i - 1] != '?'):
			return 0
		if s[i] == s[n - i - 1] == '?':
			res = res * 26 % MOD
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(str)
		res = solve(*(arg1,))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


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)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if n == 1 and s[0] == '?':
		print(26)
	else:
		count = 1
		left = 0
		right = n - 1
		while left <= right:
			if s[left] == '?' and s[right] == '?':
				left += 1
				right -= 1
				count = count * 26 % 10000009
			elif s[left] == '?' or s[right] == '?' or s[left] == s[right]:
				left += 1
				right -= 1
				continue
			else:
				count = 0
				break
		print(count)


t = int(input())
for _ in range(t):
	s = input()
	s = [i for i in s]
	n = len(s)
	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)


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)


t = int(input())
while t > 0:
	t -= 1
	s = input()
	n = len(s)
	l = 0
	r = n - 1
	count = 0
	imposible = False
	while l <= r:
		if s[l] == '?' and s[r] == '?':
			count += 1
		elif s[l] != '?' and s[r] != '?' and (s[l] != s[r]):
			imposible = True
		l += 1
		r -= 1
	if imposible == True:
		print('0')
	else:
		ans = 1
		for i in range(count):
			ans = ans * 26 % 10000009
		print(ans)


T = int(input())
for i in range(T):
	s = input()
	x = 0
	y = len(s) - 1
	z = 1
	while x <= y:
		if s[x] == '?' == s[y]:
			z = z * 26 % 10000009
		elif s[x] != '?' and s[y] != '?' and (s[x] != s[y]):
			z = 0
			break
		x += 1
		y -= 1
	print(z)


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)


for _ in range(int(input())):
	s1 = str(input())
	n = len(s1)
	ans = 1
	for i in range((n + 1) // 2):
		if s1[i] == '?' and s1[n - i - 1] == '?':
			ans = ans * 26 % 10000009
		elif s1[i] != '?' and s1[n - i - 1] != '?' and (s1[i] != s1[n - i - 1]):
			ans = 0
			break
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			if s[i] != '?' and s[n - 1 - i] != '?':
				print(0)
				break
		elif s[i] == '?' and s[n - i - 1] == '?':
			count += 1
	else:
		if n & 1 == 1:
			if s[n // 2] == '?':
				count += 1
		print(pow(26, count, 10000009))


tc = int(input())
for _ in range(tc):
	s = input()
	n = len(s)
	ans = 1
	for i in range(n // 2):
		x = (s[i] == '?') + (s[n - i - 1] == '?')
		if x == 2:
			ans = ans * 26 % 10000009
		elif x == 0 and s[i] != s[n - i - 1]:
			ans = 0
			break
	if n % 2 == 1 and s[n // 2] == '?':
		ans *= 26
	print(ans)


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)


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)


mod = 10000009
t = int(input())
while t:
	t = t - 1
	s = input()
	i = 0
	j = len(s) - 1
	c = 1
	while i <= j:
		if s[i] == '?' and s[j] == '?':
			c = c * 26 % mod
		elif s[i] == '?' or s[j] == '?':
			pass
		elif s[i] != s[j]:
			c = 0
			break
		i = i + 1
		j = j - 1
	print(c % mod)


T = int(input())
for _ in range(T):
	r = input()
	n = len(r)
	(a, b, c) = (0, n - 1, 1)
	while a <= b:
		if r[a] == '?' == r[b]:
			c = c * 26 % 10000009
		elif r[a] != '?' and r[b] != '?' and (r[a] != r[b]):
			c = 0
			break
		a += 1
		b -= 1
	print(c)


tests = int(input())
for i in range(tests):
	string = input()
	length = len(string)
	ans = 1
	end = (length - 1) // 2 + 1
	for j in range(end):
		if string[j] == '?' and string[-j - 1] == '?':
			ans *= 26
		elif string[j] == '?' or string[-j - 1] == '?':
			ans *= 1
		elif string[j] != string[-j - 1]:
			ans = 0
			break
		ans %= 10000009
	print(ans)


for t in range(0, int(input())):
	string = input()
	count = 0
	r = 0
	k = len(string)
	if k % 2 != 0:
		if string[k // 2] == '?':
			count += 1
	for i in range(0, len(string) // 2):
		if string[i] == '?' and string[k - 1] == '?':
			count += 1
		elif string[i] != string[k - 1] and string[i] != '?' and (string[k - 1] != '?'):
			r = 1
			break
		k -= 1
	if r == 1:
		print(0)
	else:
		ans = 1
		for i in range(0, count):
			ans = ans * 26 % 10000009
		print(ans)


for _ in range(int(input())):
	s = input()
	i = 0
	j = len(s) - 1
	cnt = 1
	f = 1
	while i <= j:
		if s[i] == '?' and s[j] == '?':
			cnt = cnt * 26 % 10000009
		elif s[i] == '?' or s[j] == '?':
			pass
		elif s[i] != s[j]:
			f = -1
			break
		i += 1
		j -= 1
	if f == -1:
		print(0)
	else:
		print(cnt)


for _ in range(int(input())):
	recipe = input()
	n = len(recipe)
	i = 0
	j = n - 1
	ans = 1
	while i <= j:
		if recipe[i] == '?' and recipe[j] == '?':
			ans = ans * 26 % 10000009
		elif recipe[i] == '?' or recipe[j] == '?':
			pass
		elif recipe[i] != recipe[j]:
			ans = 0
			break
		i += 1
		j -= 1
	print(ans % 10000009)


MOD = 10000009

def solve():
	s = input()
	ls = len(s)
	res = 1
	if ls == 1:
		if s[0] == '?':
			print(26)
		else:
			print(1)
		return
	if ls & 1:
		for i in range(ls // 2):
			first_ch = s[i]
			last_ch = s[ls - i - 1]
			if first_ch == '?' and last_ch == '?':
				res = res * 26 % MOD
			elif first_ch == '?' or last_ch == '?':
				res = res * 1 % MOD
			elif first_ch != last_ch:
				res = res * 0 % MOD
		if s[ls // 2] == '?':
			res = res * 26 % MOD
	else:
		for i in range(ls // 2):
			first_ch = s[i]
			last_ch = s[ls - i - 1]
			if first_ch == '?' and last_ch == '?':
				res = res * 26 % MOD
			elif first_ch == '?' or last_ch == '?':
				res = res * 1 % MOD
			elif first_ch != last_ch:
				res = res * 0 % MOD
	print(res)
for _ in range(int(input())):
	solve()


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)
			elif start != end:
				if start != '?' and end != '?':
					ans = 0
					break
	print(ans)


t = int(input())
for i in range(t):
	q = input()
	l = len(q)
	ans = 1
	mod = 10 ** 7 + 9
	for j in range((l + 1) // 2):
		if q[j] != q[l - 1 - j] and q[j] != '?' and (q[l - 1 - j] != '?'):
			ans = 0
			break
		elif q[j] == '?' and q[l - 1 - j] == '?':
			ans = ans * 26 % mod
	print(ans)


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):
		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)


for _ in range(int(input())):
	s = input()
	nWays = 1
	n = len(s)
	f = True
	for i in range(n // 2):
		if s[i] == s[-i - 1]:
			if s[i] == '?':
				nWays = nWays * 26 % (10 ** 7 + 9)
		elif s[i] == '?' and s[-i - 1] != '?' or (s[i] != '?' and s[-i - 1] == '?'):
			continue
		else:
			nWays = 0
			f = False
			break
	if f and n % 2 and (s[n // 2] == '?'):
		nWays = nWays * 26 % (10 ** 7 + 9)
	print(nWays)


for _ in range(int(input())):
	s = input()
	l = len(s)
	ans = 1
	mod = 10000009
	for i in range((l + 1) // 2):
		if s[i] == s[l - i - 1] == '?':
			ans = ans * 26 % mod
		elif s[i].isalpha() and s[l - 1 - i].isalpha() and (s[i] != s[l - i - 1]):
			ans = 0
	print(ans)


mod = 10000009
t = int(input())
for _ in range(t):
	s = input()
	ln = len(s)
	dx = 1
	for i in range(ln // 2):
		xn = ln - i - 1
		x = s[i]
		y = s[xn]
		if x == '?' and y == '?':
			dx = dx * 26 % mod
		elif x == y:
			continue
		elif x == '?' or y == '?':
			continue
		else:
			dx = 0
			break
	if ln % 2 == 1 and ln > 1:
		if s[ln // 2] == '?':
			dx = dx * 26 % mod
	elif ln == 1:
		if s == '?':
			dx = 26 % mod
	print(dx)


mod = 10000009
for _ in range(int(input())):
	st = input()
	c = 1
	i = 0
	j = len(st) - 1
	while i <= j:
		if st[i] == '?' and st[j] == '?':
			c = c * 26 % mod
		elif st[i] == '?' or st[j] == '?':
			pass
		elif st[i] != st[j]:
			c = 0
			break
		i = i + 1
		j = j - 1
	print(c % mod)


for _ in range(int(input())):
	str1 = str(input())
	n = len(str1)
	(a, b, c) = (0, n - 1, 1)
	while a <= b:
		if str1[a] == '?' == str1[b]:
			c = c * 26 % 10000009
		elif str1[a] != '?' and str1[b] != '?' and (str1[a] != str1[b]):
			c = 0
			break
		a += 1
		b -= 1
	print(c)


t = int(input())
for i in range(t):
	x = input()
	n = len(x)
	a = 0
	b = n - 1
	count = 1
	while a <= b:
		if x[a] == '?' == x[b]:
			count = count * 26 % 10000009
		elif x[a] != '?' and x[b] != '?' and (x[a] != x[b]):
			count = 0
			break
		a += 1
		b -= 1
	print(count)


t = int(input())
for i in range(t):
	x = input()
	y = len(x)
	ans = 1
	modulo = 10 ** 7 + 9
	for j in range((y + 1) // 2):
		if x[j] != x[y - 1 - j] and x[j] != '?' and (x[y - 1 - j] != '?'):
			ans = 0
			break
		elif x[j] == '?' and x[y - 1 - j] == '?':
			ans = ans * 26 % modulo
	print(ans)


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)


try:
	for _ in range(0, int(input())):
		x = input()
		l = len(x)
		ans = 1
		u = 0
		v = l - 1
		while u <= v:
			if x[u] == '?' and x[v] == '?':
				ans = ans * 26 % 10000009
			elif x[u] != '?' and x[v] != '?' and (x[u] != x[v]):
				ans = 0
				break
			u += 1
			v -= 1
		print(ans)
except:
	pass


t = int(input())
mod = 10000009
while t:
	s = input()
	m = len(s)
	ans = 1
	for i in range(m // 2 + 1):
		if i == m // 2 and m & 1 == 0:
			break
		if (s[i] != '?' and s[-(i + 1)] != '?') and s[i] != s[-(i + 1)]:
			ans = 0
			break
		if s[i] == s[-(i + 1)] == '?':
			ans = ans * 26 % mod
	print(ans % mod)
	t -= 1


for _ in range(int(input())):
	pal = input().strip()
	mul = 0
	flag = True
	if len(pal) % 2 == 0:
		till = len(pal) // 2
	else:
		till = len(pal) // 2 + 1
	for i in range(till):
		(left, right) = (pal[i], pal[len(pal) - i - 1])
		if left == '?':
			if right == '?':
				mul += 1
		elif right == '?':
			continue
		elif left != right:
			flag = False
			break
	if flag:
		print(max(26 ** mul, 1) % 10000009)
	else:
		print('0')


for _ in range(int(input())):
	S = input()
	possible = 1
	(start, end) = (0, len(S) - 1)
	flag = True
	while start <= end:
		if S[start] == '?' and S[end] == '?':
			possible = possible * 26 % 10000009
		elif S[start] != '?' and S[end] != '?' and (S[start] != S[end]):
			print(0)
			flag = False
			break
		start += 1
		end -= 1
	if flag:
		print(possible)


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


for _ in range(int(input())):
	s = input()
	l = len(s)
	flag = False
	count = 0
	if l % 2 == 1:
		if s[l // 2] == '?':
			count += 1
	for i in range(0, l // 2):
		if s[i] == '?' and s[l - i - 1] == '?':
			count += 1
		elif s[i] != s[l - i - 1] and s[i] != '?' and (s[l - i - 1] != '?'):
			flag = True
			break
	if flag:
		print(0)
	else:
		ans = 1
		for i in range(count):
			ans = ans * 26 % 10000009
		print(ans)


MOD = 10000009

def count_palindromes(s):
	n = len(s)
	count = 1
	for i in range(n // 2):
		j = n - i - 1
		if s[i] == '?' and s[j] == '?':
			count = count * 26 % MOD
		elif s[i] == s[j] or s[i] == '?' or s[j] == '?':
			continue
		else:
			return 0
	if n % 2 == 1 and s[n // 2] == '?':
		count = count * 26 % MOD
	return count
t = int(input())
for _ in range(t):
	s = input().strip()
	print(count_palindromes(s))


t = int(input())
for i in range(t):
	s = input()
	c = 1
	d = len(s)
	for i in range((d + 1) // 2):
		j = d - 1 - i
		if s[i] != '?' and s[j] != '?' and (s[i] != s[j]):
			c = 0
			break
		elif s[i] == '?' and s[j] == '?':
			c = c * 26 % 10000009
	print(c)


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


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)
t = int(input())
while t > 0:
	solve()
	t = t - 1


for t in range(int(input())):
	s = input()
	ans = 1
	b = 0
	du = len(s)
	if du == 1:
		if s[0] == '?':
			print(26)
		else:
			print(1)
	else:
		for i in range(du // 2):
			if s[i] == '?' and s[-i - 1] == '?':
				ans = ans * 26 % 10000009
			elif (s[i] == '?' or s[-i - 1] == '?') or s[i] == s[-i - 1]:
				ans = ans
			elif s[i] != s[-i - 1]:
				ans = 0
				b = 1
				print(ans % 10000009)
				break
		if du % 2 != 0:
			if s[du // 2] == '?':
				ans = ans * 26 % 10000009
		if b == 0:
			print(ans % 10000009)


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

def tri(n):
	return n * (n + 1) // 2
modulus = 10000009

def smallest_first(m, n):
	return (min(m, n), max(m, n))
from functools import reduce

def solve(s):
	if len(s) == 1:
		return 26 if s == '?' else 1
	if len(s) == 2:
		return 26 if s == '??' else 1 if any(['?' in s, s == s[::-1]]) else 0
	(left, half, end) = (0, len(s) // 2, len(s))
	adj = 1 if end & 1 else 0
	ans = reduce(lambda x, y: x * y % modulus, [26 if all([l == '?', r == '?']) else 1 if any([l == '?', r == '?', l == r]) else 0 for (l, r) in zip(s[left:half], s[end:half - 1 + adj:-1])])
	if adj:
		ans = ans * 26 % modulus if s[half] == '?' else ans
	return ans

def do_codechef():
	for t in rii():
		print(solve(si()))
do_codechef()
exit()


for _ in range(int(input())):
	q = input()
	ln = len(q)
	ans = 1
	modn = 10 ** 7 + 9
	for i in range((ln + 1) // 2):
		if q[i] != q[ln - 1 - i] and q[i] != '?' and (q[ln - 1 - i] != '?'):
			ans = 0
			break
		elif q[i] == '?' and q[ln - 1 - i] == '?':
			ans = ans * 26 % modn
	print(ans)