Problem: Whoso in ignorance draws near to them and hears the Sirens' voice, he nevermore returns.

Homer, Odyssey

In the times of Jason and the Argonauts, it was well known that sirens use the sound of their songs to lure sailors into their demise. Yet only a few knew that every time sirens call a sailor by his name, his will weakens, making him more vulnerable. 

For the purpose of this problem, both siren songs and names of the sailors will be represented as strings of lowercase English letters. The more times the sailor's name occurs as a contiguous substring of the song, the greater danger he is in.

Jason found out that sirens can sing one of the n+1 songs, which have the following structure: let s_i (0 ≤ i ≤ n) be the i-th song and t be a string of length n, then for every i < n: s_{i+1} = s_i t_i s_i. In other words i+1-st song is the concatenation of i-th song, i-th letter (0-indexed) of t and the i-th song. 

Fortunately, he also knows s_0 and t. Jason wonders how many times a sailor's name is mentioned in a particular song. Answer q queries: given the sailor's name (w) and the index of a song (i) output the number of occurrences of w in s_i as a substring. As this number can be quite large, output its remainder modulo 10^9+7.

Input

In the first line of input there are two integers n, q (  1 ≤ n, q ≤ 10^5) meaning that there are n+1 songs and q queries. In the next two lines strings s_0 and t follow (1 ≤ |s_0| ≤ 100, |t| = n). 

Next q lines describe the queries; each one contains an integer k ( 0 ≤ k ≤ n), the index of the song sung by the sirens, and a non-empty string w, which is the name of a sailor. All strings in this problem consist only of lowercase English letters, and the sum of lengths of sailors' names does not exceed 10^6.

Output

Output q lines, i-th of them should contain the remainder modulo 10^9+7 of the number of occurrences of w in s_k.

Examples

Input


3 3
aa
bcd
2 aba
3 ca
3 aa


Output


2
2
8


Input


4 5
aba
bbac
1 a
3 baca
3 ab
2 bab
4 aba


Output


4
0
14
6
28

Note

In the first example songs of the sirens are as follows: 

  * Song 0: aa
  * Song 1: aabaa
  * Song 2: aabaacaabaa
  * Song 3: aabaacaabaadaabaacaabaa

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T, size_t sz> ostream &operator<<(ostream &os, const array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
#if __cplusplus >= 201703L
template <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os; }
#endif
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl
#else
#define dbg(x) {}
#endif

template <int mod> struct ModInt {
#if __cplusplus >= 201402L
#define MDCONST constexpr
#else
#define MDCONST
#endif
    using lint = long long;
    MDCONST static int get_mod() { return mod; }
    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&]() {
                std::set<int> fac;
                int v = mod - 1;
                for (lint i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < mod; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModInt(g).pow((mod - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }
    int val;
    MDCONST ModInt() : val(0) {}
    MDCONST ModInt &_setval(lint v) { return val = (v >= mod ? v - mod : v), *this; }
    MDCONST ModInt(lint v) { _setval(v % mod + mod); }
    MDCONST explicit operator bool() const { return val != 0; }
    MDCONST ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
    MDCONST ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + mod); }
    MDCONST ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % mod); }
    MDCONST ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val * x.inv() % mod); }
    MDCONST ModInt operator-() const { return ModInt()._setval(mod - val); }
    MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    MDCONST ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    MDCONST ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
    friend MDCONST ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % mod + x.val); }
    friend MDCONST ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % mod - x.val + mod); }
    friend MDCONST ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % mod * x.val % mod); }
    friend MDCONST ModInt operator/(lint a, const ModInt &x) { return ModInt()._setval(a % mod * x.inv() % mod); }
    MDCONST bool operator==(const ModInt &x) const { return val == x.val; }
    MDCONST bool operator!=(const ModInt &x) const { return val != x.val; }
    MDCONST bool operator<(const ModInt &x) const { return val < x.val; } // To use std::map<ModInt, T>
    friend std::istream &operator>>(std::istream &is, ModInt &x) {
        lint t;
        return is >> t, x = ModInt(t), is;
    }
    MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }
    MDCONST ModInt pow(lint n) const {
        lint ans = 1, tmp = this->val;
        while (n) {
            if (n & 1) ans = ans * tmp % mod;
            tmp = tmp * tmp % mod, n /= 2;
        }
        return ans;
    }

    static std::vector<long long> facs, invs;
    MDCONST static void _precalculation(int N) {
        int l0 = facs.size();
        if (N <= l0) return;
        facs.resize(N), invs.resize(N);
        for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i % mod;
        long long facinv = ModInt(facs.back()).pow(mod - 2).val;
        for (int i = N - 1; i >= l0; i--) {
            invs[i] = facinv * facs[i - 1] % mod;
            facinv = facinv * i % mod;
        }
    }
    MDCONST lint inv() const {
        if (this->val < 1 << 20) {
            while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
            return invs[this->val];
        } else {
            return this->pow(mod - 2).val;
        }
    }
    MDCONST ModInt fac() const {
        while (this->val >= int(facs.size())) _precalculation(facs.size() * 2);
        return facs[this->val];
    }

    MDCONST ModInt doublefac() const {
        lint k = (this->val + 1) / 2;
        return (this->val & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac()) : ModInt(k).fac() * ModInt(2).pow(k);
    }
    MDCONST ModInt nCr(const ModInt &r) const { return (this->val < r.val) ? 0 : this->fac() / ((*this - r).fac() * r.fac()); }

    ModInt sqrt() const {
        if (val == 0) return 0;
        if (mod == 2) return val;
        if (pow((mod - 1) / 2) != 1) return 0;
        ModInt b = 1;
        while (b.pow((mod - 1) / 2) == 1) b += 1;
        int e = 0, m = mod - 1;
        while (m % 2 == 0) m >>= 1, e++;
        ModInt x = pow((m - 1) / 2), y = (*this) * x * x;
        x *= (*this);
        ModInt z = b.pow(m);
        while (y != 1) {
            int j = 0;
            ModInt t = y;
            while (t != 1) j++, t *= t;
            z = z.pow(1LL << (e - j - 1));
            x *= z, z *= z, y *= z;
            e = j;
        }
        return ModInt(std::min(x.val, mod - x.val));
    }
};
template <int mod> std::vector<long long> ModInt<mod>::facs = {1};
template <int mod> std::vector<long long> ModInt<mod>::invs = {0};
using mint = ModInt<1000000007>;

// Rolling Hash (Rabin-Karp), 1dim
template <typename V> struct rolling_hash {
    V B;
    vector<V> hash;  // hash[i] = s[0] * B^(i - 1) + ... + s[i - 1]
    vector<V> power; // power[i] = B^i
    rolling_hash() {}
    rolling_hash(const string &s, V b) : B(b) {
        int N = s.length();
        hash.resize(N + 1), power.resize(N + 1, 1);
        for (int i = 0; i < N; i++) {
            power[i + 1] = power[i] * B;
            hash[i + 1] = hash[i] * B + s[i];
        }
    }
    V get_hash(int l, int r) // s[l] * B^(r - l - 1) + ... + s[r - 1]
    {
        return hash[r] - hash[l] * power[r - l];
    }
};

using lint = long long;
using plint = pair<lint, lint>;
struct DoubleHash : public plint {
    static plint MODs;
    DoubleHash(plint x) : plint(x) {}
    DoubleHash(lint x, lint y) : plint(x, y) {}
    DoubleHash(lint x) : DoubleHash(x, x) {}
    DoubleHash() : DoubleHash(0) {}
    static inline DoubleHash mod_subtract(plint x) {
        if (x.first >= MODs.first) x.first -= MODs.first;
        if (x.second >= MODs.second) x.second -= MODs.second;
        return x;
    }
    DoubleHash operator+(const DoubleHash &x) const { return mod_subtract(plint(this->first + x.first, this->second + x.second)); }
    DoubleHash operator+(lint x) const { return mod_subtract(plint(this->first + x, this->second + x)); }
    DoubleHash operator-(const DoubleHash &x) const { return mod_subtract(plint(this->first - x.first + MODs.first, this->second - x.second + MODs.second)); }
    DoubleHash operator*(const DoubleHash &x) const { return make_pair(this->first * x.first % MODs.first, this->second * x.second % MODs.second); }
    DoubleHash operator*(lint x) const { return make_pair(this->first * x % MODs.first, this->second * x % MODs.second); }
};
plint DoubleHash::MODs = plint(1000000007, 998244353);

struct rand_int_ {
    using lint = long long;
    mt19937 mt;
    rand_int_() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
    lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
    lint operator()(lint l, lint r) {
        uniform_int_distribution<lint> d(l, r - 1);
        return d(mt);
    }
} rnd;

// Z algorithm (length of longest common prefix for s[0:N] & s[i:N] for each i)
// Complexity: O(N)
// <http://snuke.hatenablog.com/entry/2014/12/03/214243>
template <typename T> std::vector<int> z_algorithm(const std::vector<T> &s) {
    const int N = s.size();
    if (N == 0) return {};
    std::vector<int> ans(N);
    ans[0] = N;
    int i = 1, j = 0;
    while (i < N) {
        while (i + j < N and s[j] == s[i + j]) ++j;
        ans[i] = j;
        if (!j) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < N and k + ans[k] < j) ans[i + k] = ans[k], ++k;
        i += k;
        j -= k;
    }
    return ans;
}

std::vector<int> z_algorithm(const std::string &s) {
    const int N = int(s.size());
    std::vector<int> v(N);
    for (int i = 0; i < N; i++) v[i] = s[i];
    return z_algorithm(v);
}

int main()
{
    const plint b(rnd(1 << 5, 1 << 28), rnd(1 << 5, 1 << 29));

    int N, Q;
    string S0, T;
    cin >> N >> Q >> S0 >> T;

    string S = S0;
    int ncon = 0;
    vector<string> SS{S};
    vector<int> Ssz{int(S.length())};
    REP(i, T.size()) {
        if (S.length() <= 1e6) {
            S = S + T[i] + S;
            SS.emplace_back(S);
            Ssz.emplace_back(S.length());
            ncon++;
        } else break;
    }
    dbg(Ssz);

    array<vector<mint>, 26> dcnt;
    REP(d, 26) dcnt[d].resize(N + 1);
    REP(i, N) {
        REP(d, 26) dcnt[d][i + 1] = dcnt[d][i] * 2;
        dcnt[T[i] - 'a'][i + 1] += 1;
    }
    dbg(dcnt);

    rolling_hash<DoubleHash> RH(S, b);
    dbg(S);
    dbg(ncon);
    string aaaa = "AAAA";
    dbg(z_algorithm(aaaa));

    vector<mint> pow2(1 << 22, 1);
    FOR(i, 1, pow2.size()) pow2[i] = pow2[i - 1] * 2;

    auto solve = [&](int k, string Q) -> mint {
        if (Q.length() > S.length()) return mint(0);
        mint ret = 0;
        const int d = lower_bound(ALL(Ssz), Q.length()) - Ssz.begin();
        if (d <= k) {
            string tmp = Q + '_' + SS[d];
            auto v = z_algorithm(tmp);
            dbg(d);
            ret += mint(count(v.begin() + Q.length() + 1, v.end(), Q.length())) * pow2[k - d];
            dbg(ret);

            rolling_hash<DoubleHash> QH(Q, b);
            REP(q, Q.length()) {
                if ((QH.get_hash(0, q) == RH.get_hash(S.length() - q, S.length())) and
                    QH.get_hash(q + 1, Q.length()) == RH.get_hash(0, Q.length() - 1 - q)) {
                    dbg(q);
                    dbg((pint(k, d)));
                    dbg(dcnt[Q[q] - 'a'][k]);
                    dbg(dcnt[Q[q] - 'a'][d]);
                    ret += (dcnt[Q[q] - 'a'][k] - dcnt[Q[q] - 'a'][d] * pow2[k - d]);
                }
            }
        }
        return ret;
    };

    REP(q, Q) {
        int k;
        string Q;
        cin >> k >> Q;
        cout << solve(k, Q).val << '\n';
    }
}