#include <stdio.h>

#include <math.h>

#include<cstring>

#include<cmath>

#include<map>

#include<string>

#include<algorithm>

using namespace std;

long long mod=;

char s[+];

long long num[+];

long long extend_gcd(long long a,long long b,long long &x,long long &y)

{

    if(a==&&b==) return -;

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    long long d=extend_gcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

long long mod_reverse(long long a,long long n)

{

    long long x,y;

    long long d=extend_gcd(a,n,x,y);

    if(d==) return (x%n+n)%n;

    else return -;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        scanf("%s",s);

        int len=strlen(s);

        num[]=;

        for(int i=; s[i]; i++) num[i+]=s[i]-;

        for(int i=; i<=len; i++) num[i]=(num[i]*num[i-])%mod;

        for(int i=; i<=n; i++)

        {

            int li,ri;

            scanf("%d%d",&li,&ri);

            long long NI=mod_reverse(num[li-],mod);

            long long ans=(num[ri]*NI)%mod;

            printf("%lld\n",ans);

        }

    }

    return ;

}