#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lll root * 2, begin, mid
#define rrr root * 2 + 1, mid + 1, end
using namespace std;
int N;
char s[100050];
int a[100050 << 2];
int len;
int cnt;
void build(int root, int begin, int end)
{
    int mid = (begin + end) / 2;
    if(begin == end)
    {
        a[root] = (s[begin - 1] - 28) % 9973;
        //printf("%d:%d ",a[root],root);
        return ;
    }
    int k1 = 1, k2 = 1;
    build(lll);
    build(rrr);
    a[root] = (a[root << 1] * a[root << 1 | 1]) % 9973;
}
int query(int root, int begin, int end, int left, int right)
{
    int mid = (begin + end) / 2;
    if(left <= begin && end <= right)
    {
        return a[root];
    }    
    int k1 = 1;
    int k2 = 1;
    if(mid >= left)
    k1 = query(lll, left, right);
    if(mid < right)
    k2 = query(rrr, left, right);
    return k1 * k2 % 9973;
}
int main()
{
    int t;
    while(~scanf("%d", &N))
    {
        scanf("%s", s);
        len = strlen(s);
        //printf("%d\n",'t');
        build(1,1,len);
        /*for(int i = 0;i < len << 4;i ++)
            printf("%d ",a[i]);
            puts("");*/
        while(N--)
        {
            int left,right;
            scanf("%d %d",&left, &right);
            if(len <= 100000&&len >= 1)
                t = query(1,1,len,left,right);
            printf("%d\n",t);
        }
    }        
    return 0;
}