双哈希

int mod = 1000000513;

using Hash = array<int, 2>;
Hash P = {342325337, 342325331};
int norm(int x) {
  if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}

Hash operator * (const Hash& a, const Hash& b) {
  return {(int)(1LL * a[0] * b[0] % mod), (int)(1LL * a[1] * b[1] % mod)};
}

Hash operator + (const Hash& a, const Hash& b) {
   return {norm(a[0] + b[0]), norm(a[1] + b[1])};
}

Hash operator - (const Hash& a, const Hash& b) {
   return {norm(a[0] - b[0]), norm(a[1] - b[1])};
}

Hash operator * (const Hash& a, int b) { return a * Hash{b, b}; }
Hash operator + (const Hash& a, int b) { return a + Hash{b, b}; }
Hash operator - (const Hash& a, int b) { return a - Hash{b, b}; }
ostream &operator<<(ostream &os, const Hash &a) {
    return os << a[0] << " " << a[1];
}

struct H {
  vector<Hash> p, pre;
  H(string& s) {
    int n = s.size();
    p.resize(n + 1);
    pre.resize(n + 1);
    p[0] = {1, 1};
    for (int i = 0; i < n; ++i) {
      pre[i + 1] = pre[i] * P + (s[i]);
      p[i + 1] = p[i] * P;
    }
  }
  Hash query(int L, int R) {
    return pre[R + 1] - pre[L] * p[R - L + 1];
  }
};