字符串哈希

const int mod = 1000000513;
const int P = 3000017;

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