struct hash{
    const int P = 1313131; int n,mod,f[N],p[N]; char str[N];
    inline int calc(int l,int r) {
        return (1ll * f[r] - 1ll * f[l-1] * p[r - l + 1] % mod + mod) % mod;
    }
    inline void init(int Mod,char s[]){
        mod = Mod; n = strlen(s); for (int i = 0; i < n; i++) str[i] = s[i];
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = 1ll * p[i-1]  * P % mod;
            f[i] = (1ll * f[i-1] * P + (s[i-1]  - 'a')) % mod;
        }
    }
};