#include #include using namespace std; const int N = 100005; const int mod = 9973; char str[N]; int T,n,i,l,r; int las; struct seg { int l,r,val; }t[N<<2]; void build(int l,int r,int k) { t[k].l = l; t[k].r = r; t[k].val = 1; if(l == r) { t[k].val = str[l] - 28; return; } int mid = l + r >> 1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); t[k].val = (t[k<<1].val * t[k<<1|1].val) % mod; } int query(int l,int r,int k) { if(t[k].l == l && t[k].r == r) return t[k].val; int ret = 1,mid = t[k].l + t[k].r >> 1; if(r <= mid) return query(l,r,k<<1); else if(l > mid) return query(l,r,k<<1|1); else return (query(l,mid,k<<1) * query(mid+1,r,k<<1|1)) % mod; } int main() { while(~scanf("%d",&T)) { scanf("%s",str + 1); n = strlen(str + 1); build(1,n,1); while(T--) { scanf("%d%d",&l,&r); if(l > r) swap(l,r); if(l < 1 || r < 1 || l > n || r > n) printf("%d\n",las); else printf("%d\n",las = query(l,r,1)); } } return 0; }