#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
int hash[N],i,l,r,m,n;char st[N];
int sqr(int x)
{return x*x%9973;}
int ksm(int x,int y)
{
    if (y==0)return 1;
    if (y==1)return x;
    if (y&1)return sqr(ksm(x,y/2))*x%9973;
        else return sqr(ksm(x,y/2));
}
int gethash(int l,int r)
{
    return hash[r]*ksm(hash[l],9971)%9973;
}
int main()
{
    //printf("%d\n",ksm(2,10));
    while (scanf("%d",&m)!=EOF)
    {
        //puts("YES");
        scanf("%s",st+1);
        n=strlen(st+1);
        //printf("len %d\n",n);
        hash[0]=1;
        for (i=1;i<=n;i++)
            hash[i]=hash[i-1]*(st[i]-28)%9973;
        //puts("OK");
        for (i=1;i<=m;i++)
        {
            //puts("OK");
            scanf("%d%d",&l,&r);
            printf("%d\n",gethash(l-1,r));
        }
    }
}