#include typedef int ll; const ll di=9973; const ll maxn=1000009; ll dp[maxn]; char s[maxn]; void gcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} gcd(b,a%b,y,x); y-=x*(a/b); } int main(){ ll a,b,c,d,e,f,g,h; while(~scanf("%d",&a)){ scanf("%s",s); dp[0]=1; for(d=1;s[d-1];d++){ dp[d]=dp[d-1]*(ll)(s[d-1]-28); dp[d]%=di; } while(a--){ scanf("%d%d",&e,&f); e=dp[e-1],f=dp[f]; gcd(di,e,c,d); d*=f; d%=di; d=(d+di)%di; printf("%d\n",d); } } return 0; }