#include "brperm.h"
#include <iostream>
#define endl '\n'
using namespace std;
const int MAXN = 500000;
const int LOG = 20;
const int BASE = 26;
const int MOD = 1000000007;
int n;
int pw[MAXN + 1];
struct Hash
{
int len;
int num;
};
Hash operator + (Hash h1, Hash h2)
{
Hash ret;
ret.len = h1.len + h2.len;
ret.num = (1ll * h1.num * pw[h2.len] + h2.num) % MOD;
return ret;
}
bool operator == (Hash h1, Hash h2)
{
return (h1.len == h2.len and h1.num == h2.num);
}
Hash h1[MAXN + 1][LOG + 1];
Hash h2[MAXN + 1][LOG + 1];
void init(int n0, const char s[])
{
n = n0;
pw[0] = 1;
for (int i = 1; i <= MAXN; ++ i)
{
pw[i] = (1ll * pw[i - 1] * BASE) % MOD;
}
for (int i = 0; i < n; ++ i)
{
h1[i][0].len = 1;
h1[i][0].num = s[i] - 'a';
}
for (int j = 1; j <= LOG; ++ j)
{
for (int i = 0; i < n - (1ll << (j - 1)); ++ i)
{
h1[i][j] = h1[i][j - 1] + h1[i + (1ll << (j - 1))][j - 1];
}
}
for (int j = 0; j <= LOG; ++ j)
{
for (int i = 0; i < n; ++ i)
{
h2[i][j].len = 1;
h2[i][j].num = s[i] - 'a';
}
for (int k = j - 1; k >= 0; -- k)
{
for (int i = 0; i < n - (1ll << k); ++ i)
{
h2[i][j] = h2[i][j] + h2[i + (1ll << k)][j];
}
}
}
return;
}
int query(int pos, int k)
{
if (pos + (1ll << k) > n) return 0;
return (h1[pos][k] == h2[pos][k]);
}
