wa #9

wrong answer 599th numbers differ - expected: '0', found: '999999717'

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int nxt[N*20], w[N], c[N][30];
string op, s;
const int mod = 1e9 + 7;
int kmp(string S, string T) {
    int n = S.size(), m = T.size(), res = 0;
    S = " " + S, T = " " + T;
    memset(nxt, 0, sizeof(int) * (m + 3));
    for(int i = 2, j = 0; i <= m; i++) {
        while(j && T[i] != T[j + 1]) j = nxt[j];
        if(T[i] == T[j + 1]) ++j;
        nxt[i] = j;
    }
    for(int i = 1, j = 0; i <= n; i++) {
        while(j && (j == m || S[i] != T[j + 1])) j = nxt[j];
        if(S[i] == T[j + 1]) ++j;
        if(j == m) res++;
    }
    return res;
}

int qpow(int a, int b = mod - 2) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, q; cin >> m >> q;
    cin >> s >> op;
    op = " " + op;
    for(int i = m; i >= 0; i--) {
        w[i] = w[i + 1] * 2 % mod;
        if(i == m) w[m] = 1;
        for(int j = 1; j <= 26; j++) {
            c[i][j] = c[i + 1][j];
            if(op[i] == j + 'a' - 1) c[i][j] = (c[i][j] + w[i]) % mod;
        }
    }
    while(q--) {
        int k; string t, str = s; cin >> k >> t; int inv = qpow(qpow(2, m - k));
        int ans = kmp(s, t) * w[0] % mod * inv % mod, i, len = t.size();
        for(i = 1; str.size() < len && i <= m; i++) {
            int pos = str.size();
            str = str + op[i] + str;
            int beg = pos - len + 1;
            ans = (ans + kmp(str.substr(max(0ll, beg), 2 * len - 1), t) * w[i] % mod * inv % mod) % mod;
        }
        if(i <= m) {
            for(int j = 1; j <= 26; j++) {
                int pos = str.size();
                string tmp = str + char(j + 'a' - 1) + str;
                int beg = pos - len + 1;
                ans = (ans + kmp(tmp.substr(beg, 2 * len - 1), t) * (c[i][j] - c[k+1][j] + mod) % mod * inv % mod) % mod;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}