#include <bits/stdc++.h>
using namespace std;
int const BASE=31;
int const MOD=1e9+7;
int const NMAX=500005;
int const LOG=19;
int bexp[LOG];
int hsh[NMAX][LOG];
int dp[NMAX][LOG];
int nn;
void get_bexp(){
bexp[0]=BASE;
int i;
for(i=1;i<LOG;++i)
bexp[i]=1LL*bexp[i-1]*bexp[i-1]%MOD;
}
void get_hsh(int n,const char s[]){
int i,j;
for(j=0;j<LOG;++j){
hsh[0][j]=s[0]-'a'+1;
for(i=1;i<n;++i)
hsh[i][j]=(1LL*hsh[i-1][j]*bexp[j]%MOD+s[i]-'a'+1)%MOD;
}
}
void get_dp(int n,const char s[]){
int i,j;
for(i=0;i<n;++i)
dp[i][0]=s[i]-'a'+1;
for(j=1;j<LOG;++j)
for(i=0;i+(1<<j)<=n;++i)
dp[i][j]=(1LL*dp[i][j-1]*bexp[LOG-j-1]%MOD+dp[i+(1<<(j-1))][j-1])%MOD;
}
void init(int n,const char s[]){
nn=n;
get_bexp();
get_hsh(n,s);
get_dp(n,s);
}
int query(int i,int k){
if(i+(1<<k)-1>=nn)
return 0;
int rez1=hsh[i+(1<<k)-1][LOG-k-1];
if(i)
rez1=(rez1-1LL*hsh[i-1][LOG-k-1]*bexp[LOG-1]%MOD+MOD)%MOD;
int rez2=dp[i][k];
return (rez1==rez2);
}
