class Hashing {
private:
const int mod = (int) 1e9 + 7;
const int p = 53; // should be prime
string s;
int n;
vector<long long> h1, h2;
vector<long long> p1, p2;
public:
void init(string st) {
s = st;
n = (int) s.length();
p1.assign(n + 1, 1);
p2.assign(n + 1, 1);
for (int i = 1; i <= n; i++) {
p1[i] = p1[i - 1] * p;
p2[i] = p2[i - 1] * p % mod;
}
char minChar = s[0];
for (int i = 0; i < n; i++) minChar = min(minChar, s[i]);
h1.assign(n, 0);
h2.assign(n, 0);
h1[0] = s[0] - minChar + 1;
h2[0] = (s[0] - minChar + 1) % mod;
for (int i = 1; i < n; i++) {
h1[i] = h1[i - 1] + p1[i] * (s[i] - minChar + 1);
h2[i] = (h2[i - 1] + p2[i] * (s[i] - minChar + 1)) % mod;
}
}
long long getHash1(int l, int r) {
long long h = h1[r];
if (l > 0)
h -= h1[l - 1];
h *= p1[n - 1 - r];
return h;
}
long long getHash2(int l, int r) {
long long h = h2[r];
if (l > 0)
h = (h - h2[l - 1] + mod) % mod;
h = h * p2[n - 1 - r] % mod;
return h;
}
pair<long long, long long> getHash(int l, int r) {
return {getHash1(l, r), getHash2(l, r)};
}
};