#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
const int b = 177013, mod = 1e9 + 9, h = 20;
long long int l[500005][21], p[25], c[500005][21], n;
long long int power(long long int a, long long int k) {
long long int res = 1, h = a;
while (k) {
if (k & 1) res = res * h % mod;
h = h * h % mod;
k >>= 1;
}
return res;
}
void init(int nn, const char s[]) {
n = nn;
for (int i = 1; i <= n; i++) l[i][0] = s[i - 1];
p[0] = b;
for (int i = 1; i <= h; i++) p[i] = p[i - 1] * p[i - 1] % mod;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= n - (1 << i) + 1; j++) {
l[j][i] = (l[j][i - 1] + p[h - i] * l[j + (1 << i - 1)][i - 1]) % mod;
}
}
for (int i = 0; i <= h; i++) {
for (int j = n; j >= 1; j--) {
c[j][i] = (c[j + 1][i] * p[h - i] + s[j - 1]) % mod;
}
}
}
int query(int x, int k) {
x++;
int y = x + (1 << k) - 1;
if (y > n) return 0;
long long int d = c[x][k] - c[y + 1][k] * power(p[h - k], (1 << k)) % mod;
if (d < 0) d += mod;
if (l[x][k] == d) return 1;
return 0;
}
