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

数学计算问题。

注意：

1 模的操作： 乘积的模等于模的乘积， 和的模等于模的和再模等操作

可以巧妙的简化为一个计算了：

有？的时候，两边相等*26， 不等就为零了

#pragma once
#include <stdio.h>

class RecipeReconstruction
{
	const static int MOD_V = 10000009;
	const static int MAX_S = 1000001;
	const static int MAX_BUF = 5120;
	int st, len;
	char inBuf[MAX_BUF];

	char getFromBuf()
	{
		if (st >= len)
		{
			len = fread(inBuf, 1, MAX_BUF, stdin);
			st = 0;
		}
		return inBuf[st++];
	}

public:
	RecipeReconstruction() : st(0), len(0)
	{
		int T = 0, id = 0, begin = 0;
		scanf("%d", &T);
		getchar();
		char str[MAX_S], c;
		while (T--)
		{
			id = 0;
			while ((c = getFromBuf()) != ‘\n‘ && len)
			{
				str[id++] = c;
			}
			int ans = 1, mid = (id+1) >> 1;
			for (int i = 0; i < mid; i++)
			{
				if (str[i] == str[id - i - 1])
				{
					if (str[i] == ‘?‘) ans = (ans * 26) % MOD_V;
				}
				else
				{
					if (str[i] != ‘?‘ && str[id - i - 1] != ‘?‘)
					{
						ans = 0;
						break;
					}
				}
			}
			printf("%d\n",ans);
		}
	}
};

int recipeReconstruction()
{
	RecipeReconstruction();
	return 0;
}