#include<stdio.h>
#include<string.h>
char c[100005];
int a[100005];
int  quickmod(int a,int b,int c)
{
    int num=1;
    a=a%c;
    while(b>0)
    {
        if(b%2==1)
        {
             num=(num*a)%c;
        }
        b/=2;
        a=(a*a)%c;
    }
    return num;
}

int main()
{
    int n,s,e,f;
    while(~scanf("%d",&n))
    {
        scanf("%s",c);
        int n1=strlen(c);
        a[0]=1;
        for(int i=0;i<n1;i++)
            a[i+1]=(a[i]*(c[i]-28)%9973)%9973;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&s,&e);
            f=quickmod(a[s-1],9971,9973);
            printf("%d\n",(a[e]*f%9973)%9973);
        }
    }
    return 0;
}