hash

template<const int BASE, const int MODULO>
class Hashing {
private:
	typedef long long ll;
	vector<int> ipow, hash;
	int n;
	template<typename T>
	void create_hash(const T * str) {
		ipow.resize(n);
		hash.resize(n);
		
		ipow[0] = 1;
		hash[0] = str[0];
 
		ll inv = pow_(Base, Modulo - 2, Modulo);
		ll prv = 1;
 
		for(int i = 1; i < n; ++i) {
			prv = prv * Base % Modulo;
			ipow[i] = ipow[i-1] * inv % Modulo;
			hash[i] = hash[i-1] + prv * str[i] % Modulo;
			if(hash[i] >= Modulo) hash[i] -= Modulo;
		}
	}
public:
	Hashing (string & s) : n(s.size()) { create_hash(s.data()); }
	template<typename T>
	Hashing (const T * s, int n_) : n(n_) { create_hash(s); }
 
	int get_hash(int s = 0, int e = -1) {
		if (e == -1) e += n; 
		ll ans = hash[e];
		if(s > 0) {
			ans = ans - hash[s-1];
			if(ans < 0) ans += Modulo;
			ans = ans * ipow[s] % Modulo;
		}
		return ans;
	}
	const int Base = BASE;
	const int Modulo = MODULO;
};