codechef RRECIPE - "recipe reconstruction" solution

codechef RRECIPE - "recipe reconstruction": http://www.codechef.com/problems/RRECIPE

editorial: http://discuss.codechef.com/questions/2554/rrecipe-editorial

codechef RRECIPE - "recipe reconstruction" solution: http://ideone.com/7O3u5f

#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;

}