zxwgl | 2016-05-14 15:51:17
# 3
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 100002
#define BASE 28
#define MOD 9973
#define DIM 256
int n;
char str[N];
//int sum[N][DIM];
int sum[N];
void read()
{
scanf("%s", str);
}
int exponent(int a, int x)
{
int res = 1;
if( a<0 ) a+=MOD;
int tmp = a;
while(x)
{
if(x&1) res = (res*tmp)%MOD;
tmp = (tmp*a)%MOD;
x >>= 1;
}
return res;
}
int res = 1;
void solve()
{
int len = strlen(str);
for(int i=1; i<=len; ++i)
{
sum[i] = (str[i-1]+MOD-BASE)*sum[i-1]%MOD;
}
int a, b;
for(int i=0; i<n; ++i)
{
scanf("%d%d", &a, &b);
if(a<1||a>len||b<1||b>len)
goto OUTPUT;
for(int j=0; j<MOD; ++j)
{
if( sum[a-1]*j%MOD == sum[b] )
{
res = j;
break;
}
}
OUTPUT:
printf("%d\n", res);
}
}
int main()
{
sum[0] = 1;
while(scanf("%d", &n)==1)
{
read();
solve();
}
}
