String Hashing

const int maxN = 2100;

struct StringHash {
	const int64_t p = 31;
	const int64_t m = 1e9 + 7;
	int64_t h[maxN],inv[maxN];
	inline int64_t bin_pow (int64_t a,int64_t b) {
		a %= m;
		int64_t res = 1;
		while (b > 0) {
			if (b & 1) res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	inline void compute_hash (string & s) {
		int64_t p_pow = 1;
		inv[0] = 1;
		h[0] = s[0] - 'a' + 1;
		for (int i = 1; i < (int) s.size(); ++i) {
			p_pow = (p_pow * p) % m;
			inv[i] = bin_pow(p_pow,m - 2);
			h[i] = (h[i - 1] + (s[i] - 'a' + 1) * p_pow) % m;
		}
	}
	inline int64_t sub_hash (int l,int r) {
		int64_t res = h[r];
		if (l > 0) res -= h[l - 1];
		res = (res * inv[l]) % m;
		if (res < 0) res += m;
		return res;
	}
	inline int64_t single_hash (string & s) {
		int64_t hash_value = 0;
		int64_t p_pow = 1;
		for (int i = 0; i < (int) s.size(); ++i) {
			hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
			p_pow = (p_pow * p) % m;
		}
		return hash_value;
	}
};