#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <string.h>
#include <map>

using namespace std;

#define MOD 1000000009
#define M 26
 
int maxCount=0;
std::map<int,long long> mapCount;
std::set<int> lenSet;
typedef std::map<int, long long>::iterator miter;

/* Utility function to count frequencies and checking
    whether letter can make a palindrome or not */
bool isPalin(string str, int* freq)
{
    /* Initialising frequency array with all zeros */
    memset(freq, 0, M * sizeof(int));
    int l = str.length();
 
    /* Updating frequency according to given string */
    for (int i = 0; i < l; i++)
        freq[str[i] - 'a']++;
 
    int odd = 0;
 
    /* Loop to count total letter with odd frequency */
    for (int i = 0; i < M; i++)
        if (freq[i] % 2 == 1)
            odd++;
 
    /* Palindrome condition :
    if length is odd then only one letter's frequency must be odd
    if length is even no letter should have odd frequency */
    if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
        return true;
    else
        return false;
}
 
/* Utility function to reverse a string */
string reverse(string str)
{
    string rev = str;
    reverse(rev.begin(), rev.end());
    return rev;
}

long long getAllPossiblePalindromes(string substr, int x, int y)
{
    int freq[M];
    int palin_count=0;
 
    string str=substr.substr(x,y);
    // checking whether letter can make palindrome or not
    if (!isPalin(str, freq))
        return 0;
 
    int l = str.length();
 
    // half will contain half part of all palindromes,
    // that is why pushing half freq of each letter
    string half = "";
    char oddC;
    for (int i = 0; i < M; i++)
    {
        /* This condition will be true at most once */
        if(freq[i] % 2 == 1)
            oddC = i + 'a';
 
        half += string(freq[i] / 2, i + 'a');
    }
 
    /* palin will store the possible palindromes one by one */
    string palin;
 
    // Now looping through all permutation of half, and adding
    // reverse part at end.
    // if length is odd, then pushing oddCharacter also in mid
    do {
        palin = half;
        if (l % 2 == 1)
            palin += oddC;
        palin += reverse(half);
        lenSet.insert(palin.size());
        palin_count=(palin_count+1)%MOD;
        miter it=mapCount.find(palin.size());
        if (it==mapCount.end()) {
          mapCount[palin.size()]=1;
        } else {
          long long c=mapCount[palin.size()];
          c=(c+1)%MOD;
          mapCount[palin.size()]=c;
        }
        
    } while (next_permutation(half.begin(), half.end()));
    return mapCount[*lenSet.rbegin()];
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int q,l,r;
    string s;
    
    cin >> s;
    cin >> q;
    
    while(q--) {
        cin >> l >> r;
        cout << getAllPossiblePalindromes(s,l-1,r) << endl;
    }
    
    return 0;
}