#include <bits/stdc++.h>

using namespace std;
int lps(string str)
{
   int n = str.length();
   int i, j, cl;
   int L[n][n];  
   for (i = 0; i < n; i++)
      L[i][i] = 1;
    for (cl=2; cl<=n; cl++)
    {
        for (i=0; i<n-cl+1; i++)
        {
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
               L[i][j] = 2;
            else if (str[i] == str[j])
               L[i][j] = L[i+1][j-1] + 2;
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]);
        }
    }
 
    return L[0][n-1];
}

int answerQuery(string s) {
    int ans=lps(s);
    return ans%1000000007;
}

int main() {
    string s;
    cin >> s;
    int q;
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int l;
        int r;
        cin >> l >> r;
        string p=s.substr(l-1,r-l);
        int result = answerQuery(p);
        cout << result << endl;
    }
    return 0;
}