func_code_string: #include <bits/stdc++.h>         using namespace std;         const int ALPH =  z  -  a  + 1;   const int W = 1000 * 1000;      const int MOD = 1000 * 1000 * 1000 + 7;         template <typename T>   vector <int> computePrefPref(const T &s) {       int n = s.size();       vector <int> res(n + 1, 0);          int i = 1, t = 0;       while (i < n) {           while (i + t < n && s[i + t] == s[t]) {               t++;           }              res[i] = t;              int k = 1;           while (k < t && res[k] != res[i] - k) {               res[i + k] = min(res[k], res[i] - k);               k++;           }              t = max(0, t - k);           i += k;       }          res.pop_back();       return res;   }         template <typename T>   vector <bool> findOccurences(const T &s, const T &w) {       T result = w;       copy(s.begin(), s.end(), back_inserter(result));          auto pref = computePrefPref(result);          vector <bool> occ(s.size());       for (int i = 0; i < (int) s.size(); i++) {           occ[i] = pref[i + w.size()] >= w.size();       }          return occ;   }         int expo(int a, long long n, int mod) {       int ans = 1;          while (n) {           if (n & 1LL) {               ans = ((long long) ans * a) % mod;           }              n >>= 1;           a = ((long long) a * a) % mod;       }          return ans;   }      int revMod(int a, int mod) {       return expo(a, mod - 2, mod);   }         vector <long long> getPowers(int x, int n) {       vector <long long> pw(n + 1);          pw[0] = 1;       for (int i = 1; i <= n; i++) {           pw[i] = (x * pw[i - 1]) % MOD;       }          return pw;   }         int main() {       ios_base::sync_with_stdio(false);          int n, q;       cin >> n >> q;          string t; vector <string> s(1);       cin >> s[0] >> t;          while (s.size() <= n && s.back().size() <= W) {           s.push_back(s.back() + t[(int) s.size() - 1] + s.back());       }          vector <int> sLen(s.size());       for (int i = 0; i < (int) s.size(); i++) {           sLen[i] = s[i].size();       }          vector <vector<long long>> sumLetter(ALPH, vector <long long> (n + 1, 0));          auto pw = getPowers(2, n);       auto pwRev = getPowers(revMod(2, MOD), n);          for (int c = 0; c < ALPH; c++) for (int i = 1; i <= n; i++) {           sumLetter[c][i] = sumLetter[c][i - 1];              if (t[i - 1] ==  a  + c) {               sumLetter[c][i] += pwRev[i - 1];                  if (sumLetter[c][i] >= MOD) {                   sumLetter[c][i] -= MOD;               }           }       }          while (q--) {           int i; string w;           cin >> i >> w;              int k = upper_bound(sLen.begin(), sLen.end(), w.size()) - sLen.begin();           long long ans = 0;              if (i <= k) {               auto occ = findOccurences(s[i], w);                  for (bool b : occ) {                   ans += b;               }           } else {               auto occ = findOccurences(s[k], w);                  for (bool b : occ) {                   ans += b;               }                  ans = (ans * pw[i - k]) % MOD;                  string result = w + s[k] + string(1,    ) + s[k];                  int idx = w.size() + s[k].size();               int tmpSize = result.size() - w.size();                  int sn = s[k].size();                  for (int c = 0; c < ALPH; c++) {                   result[idx] =  a  + c;                   auto pref = computePrefPref(result);                      long long here = 0;                   for (int j = sn - w.size() + 1; j <= sn; j++) {                       here += pref[j + w.size()] >= w.size();                   }                      long long mul = sumLetter[c][i] - sumLetter[c][k];                   if (mul < 0) {                       mul += MOD;                   }                      mul = (mul * pw[i - 1]) % MOD;                   ans = (ans + here * mul) % MOD;               }           }              cout << ans <<   n ;       }          return 0;   }   