#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main() {
	int t, r, n;
	char s[1000005];
	scanf("%d", &t);
	while(t--) {
		scanf("%s", s); 
		r=1; n=strlen(s);
		if(n%2==0) {
			for(int i=0; i<n/2; i++) {
				if(s[i]=='?' && s[n-1-i]=='?') r=(r*26)%10000009;
				else if(s[i]!=s[n-1-i] && s[i]!='?' && s[n-1-i]!='?') r *= 0;
				else r=(r*1)%10000009;
			}
		}
		else {
			for(int i=0; i<(n-1)/2; i++) {
				if(s[i]=='?' && s[n-1-i]=='?') r=(r*26)%10000009;
				else if(s[i]!=s[n-1-i] && s[i]!='?' && s[n-1-i]!='?') r *= 0;
				else r=(r*1)%10000009;
			}
			if(s[(n-1)/2]=='?') r=(r*26)%10000009;
		}
		printf("%d\n", r);
	}
	return 0;
}