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 uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vector<T>>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
constexpr char ln = '\n';
template <class Container> inline int SZ(const Container& v) { return int(v.size()); }
template <class T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }
template <class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; }
template <class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; }
inline int topbit(ull x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(ull x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(ull x) { return __builtin_popcountll(x); }
inline int kthbit(ull x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
inline void YES(bool t = true) { cout << YESNO[t] << "\n"; }
inline void Yes(bool t = true) { cout << YesNo[t] << "\n"; }
template <class T> inline void drop(T x) { cout << x << "\n"; exit(0); }
inline void print() { cout << "\n"; }
template <class T> inline void print(const vector<T>& v) { for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) { cout << " "; } cout << *it; } print(); }
template <class T, class... Args> inline void print(const T& x, const Args& ... args) { cout << x << " "; print(args...); }
#ifdef MINATO_LOCAL
template <class T1, class T2> ostream& operator<<(ostream& os, pair<T1, T2> p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <size_t N, class TUPLE> void debug_tuple(ostream& os, TUPLE _) { (void)os; (void)_; }
template <size_t N, class TUPLE, class T, class ...Args> void debug_tuple(ostream &os, TUPLE t) { os << (N == 0 ? "" : ", ") << get<N>(t); debug_tuple<N + 1, TUPLE, Args...>(os, t); }
template <class ...Args> ostream& operator<<(ostream& os, tuple<Args...> t) { os << "("; debug_tuple<0, tuple<Args...>, Args...>(os, t); return os << ")"; }
string debug_delim(int& i) { return i++ == 0 ? "" : ", "; }
#define debug_embrace(x) { int i = 0; os << "{";  { x } return os << "}"; }
template <class T> ostream& operator<<(ostream& os, vector<T> v) { debug_embrace( for (T e : v) { os << debug_delim(i) << e; } ) }
template <class T, size_t N> ostream& operator<<(ostream& os, array<T, N> a) { debug_embrace( for (T e : a) { os << debug_delim(i) << e; } ) }
template <class T, size_t N> enable_if_t<!is_same_v<char, remove_cv_t<T>>, ostream>& operator<<(ostream& os, T(&a)[N]) { debug_embrace( for (T e : a) { os << debug_delim(i) << e; } ) }
template <class Key> ostream& operator<<(ostream& os, set<Key> s) { debug_embrace( for (Key e : s) { os << debug_delim(i) << e; }) }
template <class Key, class T> ostream& operator<<(ostream& os, map<Key, T> mp) { debug_embrace( for (auto e : mp) { os << debug_delim(i) << e; }) }
template <class Key> ostream& operator<<(ostream& os, multiset<Key> s) { debug_embrace( for (Key e : s) { os << debug_delim(i) << e; }) }
template <class T> ostream& operator<<(ostream& os, queue<T> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.front(); } ) }
template <class T> ostream& operator<<(ostream& os, deque<T> q) { debug_embrace( for (T e : q) { os << debug_delim(i) << e; } ) }
template <class T> ostream& operator<<(ostream& os, priority_queue<T> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.top(); } ) }
template <class T> ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.top(); } ) }
void debug_out() { cerr << endl; }
template <class T, class... Args> void debug_out(const T& x, const Args& ... args) { cerr << " " << x; debug_out(args...); }
#define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__)
#else
#define debug(...) (void(0))
#endif
struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(7); }; } fast_ios_;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template <int m> 
struct ModInt {
  public:
    static constexpr int mod() { return m; }
    static ModInt raw(int v) {
        ModInt x;
        x._v = v;
        return x;
    }

    ModInt() : _v(0) {}
    ModInt(long long v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    unsigned int val() const { return _v; }

    ModInt& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    ModInt& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    ModInt operator++(int) {
        ModInt result = *this;
        ++*this;
        return result;
    }
    ModInt operator--(int) {
        ModInt result = *this;
        --*this;
        return result;
    }

    ModInt& operator+=(const ModInt& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    ModInt& operator-=(const ModInt& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    ModInt& operator*=(const ModInt& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    ModInt& operator^=(long long n) {
        ModInt x = *this;
        *this = 1;
        if (n < 0) x = x.inv(), n = -n;
        while (n) {
            if (n & 1) *this *= x;
            x *= x;
            n >>= 1;
        }
        return *this;
    }
    ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); }

    ModInt operator+() const { return *this; }
    ModInt operator-() const { return ModInt() - *this; }

    ModInt pow(long long n) const {
        ModInt r = *this;
        r ^= n;
        return r;
    }
    ModInt inv() const {
        int a = _v, b = umod(), y = 1, z = 0, t;
        for (; ; ) {
            t = a / b; a -= t * b;
            if (a == 0) {
                assert(b == 1 || b == -1);
                return ModInt(b * z);
            }
            y -= t * z;
            t = b / a; b -= t * a;
            if (b == 0) {
                assert(a == 1 || a == -1);
                return ModInt(a * y);
            }
            z -= t * y;
        }
    }

    friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) += rhs; }
    friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) -= rhs; }
    friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) *= rhs; }
    friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) /= rhs; }
    friend ModInt operator^(const ModInt& lhs, long long rhs) { return ModInt(lhs) ^= rhs; }
    friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return lhs._v != rhs._v; }
    friend ModInt operator+(long long lhs, const ModInt& rhs) { return (ModInt(lhs) += rhs); }
    friend ModInt operator-(long long lhs, const ModInt& rhs) { return (ModInt(lhs) -= rhs); }
    friend ModInt operator*(long long lhs, const ModInt& rhs) { return (ModInt(lhs) *= rhs); }
    friend ostream& operator<<(ostream& os, const ModInt& M) { return os << M._v; }
    friend istream& operator>>(istream& is, ModInt& M) { long long x; is >> x; M = x; return is; }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
};

constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;

using mint = ModInt<MOD>;

template <class M>
struct ModCombination {
  public:
    ModCombination() {}
    ModCombination(int n) : n_(n), fac_(n + 1), facinv_(n + 1) {
        assert(1 <= n);
        fac_[0] = 1;
        for (int i = 1; i <= n; i++) fac_[i] = fac_[i - 1] * i;
        facinv_[n] = M(1) / fac_[n];
        for (int i = n; i >= 1; i--) facinv_[i - 1] = facinv_[i] * i;
    }

    M fac(int k) const { 
        assert(0 <= k and k <= n_);
        return fac_[k]; 
    }
    M facinv(int k) const {
        assert(0 <= k and k <= n_); 
        return facinv_[k]; 
    }
    M inv(int k) const { 
        assert(1 <= k and k <= n_);
        return facinv_[k] * fac_[k - 1]; 
    }

    M P(int n, int k) const {
        if (k < 0 or k > n) return M(0);
        assert(n <= n_);
        return fac_[n] * facinv_[n - k];
    }
    M C(int n, int k) const {
        if (k < 0 or k > n) return M(0);
        assert(n <= n_);
        return fac_[n] * facinv_[n - k] * facinv_[k];
    }
    M H(int n, int k) const {
        if (n == 0 and k == 0) return M(1);
        return C(n + k - 1, n);
    }
    M catalan(int n) const {
        if (n == 0) return M(1);
        return C(2 * n, n) - C(2 * n, n - 1);
    }

  private:
    int n_;
    vector<M> fac_, facinv_;
};

template <class T>
struct SuffixArray {
  public:
    SuffixArray() {}
    SuffixArray(const string& s) : n_(int(s.size())), data(s.size()), inv_(s.size()) {
        vector<int> s2(n_);
        for (int i = 0; i < n_; i++) {
            data[i] = s2[i] = s[i];
        }

        sa_ = sa_is(s2,255);

        for (int i = 0; i < n_; i++) {
            inv_[sa_[i]] = i;
        }
    }
    SuffixArray(const vector<T>& s) : n_(int(s.size())), data(s), inv_(s.size()) {
        vector<int> idx(n_);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
        vector<int> s2(n_);
        int now = 0;
        for (int i = 0; i < n_; i++) {
            if (i && s[idx[i - 1]] != s[idx[i]]) now++;
            s2[idx[i]] = now;
        }

        sa_ = sa_is(s2, now);

        for (int i = 0; i < n_; i++) {
            inv_[sa_[i]] = i;
        }
    }
    SuffixArray(const vector<int>& s, int upper) : n_(int(s.size())), data(s.size()), inv_(s.size()) {
        //assert(0 <= upper);
        for (int i = 0; i < n_; i++) {
            //assert(0 <= s[i] && s[i] <= upper);
            data[i] = s[i];
        }
        
        auto sa_ = sa_is(s, upper);
        
        for (int i = 0; i < n_; i++) {
            inv_[sa_[i]] = i;
        }
    }

    int size() const { return n_; }

    int operator[](int i) const {
        //assert(0 <= i and i < n_);
        return sa_[i];
    }

    int inv(int i) const {
        //assert(0 <= i and i < n_);
        return inv_[i];
    }

    T dat(int i) const {
        //assert(0 <= i and i < n_);
        return data[i];
    }

    int lower_bound(const vector<T>& t) const {
        int l = -1, r = n_;
        while (r - l > 1) {
            int m = (l + r) / 2;
            (lt_substr(t, sa_[m]) ? l : r) = m;
        }
        return r;
    }

    int lower_bound(const string& t) const {
        vector<T> t2 = stov(t);
        int r = lower_bound(t2);
        return r;
    }

    int upper_bound(vector<T> t) const {
        if (t.empty()) return 0;
        t.back()++;
        int r = lower_bound(t);
        return r;
    }

    int upper_bound(const string& t) const {
        vector<T> t2 = stov(t);
        int r = upper_bound(t2);
        return r;
    }

    int count(const vector<T>& t) const {
        return upper_bound(t) - lower_bound(t);
    }

    // O(|T|*log|S|)
    int count(const string& t) const {
        vector<T> t2 = stov(t);
        return count(t2);
    }

  private:
    int n_;
    vector<T> data;
    vector<int> sa_, inv_;

    vector<T> stov(const string& s) const {
        int n = int(s.size());
        vector<T> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i] = s[i];
        }
        return ret;
    }

    bool lt_substr(const vector<T>& t, int pos_s) const {
        return lexicographical_compare(data.begin() + pos_s, data.end(), t.begin(), t.end());
    }

    vector<int> sa_naive(const vector<int>& s) const {
        int n = int(s.size());
        vector<int> sa(n);
        iota(sa.begin(), sa.end(), 0);
        sort(sa.begin(), sa.end(), [&](int l, int r) {
            if (l == r) return false;
            while (l < n && r < n) {
                if (s[l] != s[r]) return s[l] < s[r];
                l++;
                r++;
            }
            return l == n;
        });
        return sa;
    }

    vector<int> sa_doubling(const vector<int>& s) const {
        int n = int(s.size());
        vector<int> sa(n), rnk = s, tmp(n);
        iota(sa.begin(), sa.end(), 0);
        for (int k = 1; k < n; k *= 2) {
            auto cmp = [&](int x, int y) {
                if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
                int rx = x + k < n ? rnk[x + k] : -1;
                int ry = y + k < n ? rnk[y + k] : -1;
                return rx < ry;
            };
            sort(sa.begin(), sa.end(), cmp);
            tmp[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
            }
            swap(tmp, rnk);
        }
        return sa;
    }

    // SA-IS, linear-time suffix array construction
    // Reference:
    // G. Nong, S. Zhang, and W. H. Chan,
    // Two Efficient Algorithms for Linear Time Suffix Array Construction
    template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
    vector<int> sa_is(const vector<int>& s, int upper) const {
        int n = int(s.size());
        if (n == 0) return {};
        if (n == 1) return {0};
        if (n == 2) {
            if (s[0] < s[1]) {
                return {0, 1};
            } else {
                return {1, 0};
            }
        }
        if (n < THRESHOLD_NAIVE) {
            return sa_naive(s);
        }
        if (n < THRESHOLD_DOUBLING) {
            return sa_doubling(s);
        }

        vector<int> sa(n);
        vector<bool> ls(n);
        for (int i = n - 2; i >= 0; i--) {
            ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
        }
        vector<int> sum_l(upper + 1), sum_s(upper + 1);
        for (int i = 0; i < n; i++) {
            if (!ls[i]) {
                sum_s[s[i]]++;
            } else {
                sum_l[s[i] + 1]++;
            }
        }
        for (int i = 0; i <= upper; i++) {
            sum_s[i] += sum_l[i];
            if (i < upper) sum_l[i + 1] += sum_s[i];
        }

        auto induce = [&](const vector<int>& lms) {
            fill(sa.begin(), sa.end(), -1);
            vector<int> buf(upper + 1);
            copy(sum_s.begin(), sum_s.end(), buf.begin());
            for (auto d : lms) {
                if (d == n) continue;
                sa[buf[s[d]]++] = d;
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            sa[buf[s[n - 1]]++] = n - 1;
            for (int i = 0; i < n; i++) {
                int v = sa[i];
                if (v >= 1 && !ls[v - 1]) {
                    sa[buf[s[v - 1]]++] = v - 1;
                }
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            for (int i = n - 1; i >= 0; i--) {
                int v = sa[i];
                if (v >= 1 && ls[v - 1]) {
                    sa[--buf[s[v - 1] + 1]] = v - 1;
                }
            }
        };

        vector<int> lms_map(n + 1, -1);
        int m = 0;
        for (int i = 1; i < n; i++) {
            if (!ls[i - 1] && ls[i]) {
                lms_map[i] = m++;
            }
        }
        vector<int> lms;
        lms.reserve(m);
        for (int i = 1; i < n; i++) {
            if (!ls[i - 1] && ls[i]) {
                lms.push_back(i);
            }
        }

        induce(lms);

        if (m) {
            vector<int> sorted_lms;
            sorted_lms.reserve(m);
            for (int v : sa) {
                if (lms_map[v] != -1) sorted_lms.push_back(v);
            }
            vector<int> rec_s(m);
            int rec_upper = 0;
            rec_s[lms_map[sorted_lms[0]]] = 0;
            for (int i = 1; i < m; i++) {
                int l = sorted_lms[i - 1], r = sorted_lms[i];
                int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
                int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
                bool same = true;
                if (end_l - l != end_r - r) {
                    same = false;
                } else {
                    while (l < end_l) {
                        if (s[l] != s[r]) {
                            break;
                        }
                        l++;
                        r++;
                    }
                    if (l == n || s[l] != s[r]) same = false;
                }
                if (!same) rec_upper++;
                rec_s[lms_map[sorted_lms[i]]] = rec_upper;
            }

            auto rec_sa =
                sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

            for (int i = 0; i < m; i++) {
                sorted_lms[i] = lms[rec_sa[i]];
            }
            induce(sorted_lms);
        }
        return sa;
    }
};

struct ModInt61 {
    static constexpr ull MD = (1ULL << 61) - 1;
    using M = ModInt61;
    static constexpr ull get_mod() { return MD; }
    ull v;
    ModInt61(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(ull _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    ull val() const { return v; }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const {
        __uint128_t z = __uint128_t(v) * r.v;        
        return M().set_v(ull((z & ((1ULL << 61) - 1)) + (z >> 61)));
    }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
 
struct RollingHash {
  public:
    static inline ull generate_base() {
        mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
        uniform_int_distribution<ull> rand(0ULL, ModInt61::get_mod() - 1);
        return rand(mt);
    }

    RollingHash(int n, ull base) : n_(n), power(n + 1, 1), base_(base) {
        for (int i = 0; i < n; i++) {
            power[i+1] = power[i] * base_;
        }
    }

    int size() const { return n_ + 1; }

    ModInt61 operator[](int i) const {
        assert(0 <= i and i <= n_);
        return power[i];
    }

    ModInt61 get_base() const { return base_; }

    template <class String, int base_num = 1>
    vector<ModInt61> get_hash(const String& s) const {
        int n = int(s.size());
        //assert(n <= n_);
        vector<ModInt61> ret(n + 1);
        for (int i = 0; i < n; i++) {
            ret[i+1] = ret[i] * base_ + s[i] + base_num;
        }
        return ret;
    }

    // [l,r) (0-indexed)
    ModInt61 getrange(const vector<ModInt61>& hash, int l, int r) const {
        if (l >= r) return ModInt61(0);
        assert(0 <= l and r <= n_);
        return hash[r] - hash[l] * power[r-l];
    }

    template <class String, int base_num = 1>
    ModInt61 getval(const String& s) const {
        int n = int(s.size());
        //assert(n <= n_);
        ModInt61 ret = 0;
        for (int i = 0; i < n; i++) {
            ret = ret * base_ + s[i] + base_num;
        }
        return ret;
    }

    ModInt61 concat(ModInt61 hl, ModInt61 hr, int rlen) const {
        assert(rlen <= n_);
        return hl * power[rlen] + hr;
    }

	int LCP(const vector<ModInt61>& a, const vector<ModInt61>& b, int l1, int r1, int l2, int r2) const {
        assert(0 <= l1 and l1 < r1 and r1 < int(a.size()));
        assert(0 <= l2 and l2 < r2 and r2 < int(b.size()));
		int len = min(r1 - l1, r2 - l2);
    	int low = -1, high = len + 1;
    	while (high - low > 1) {
      		int mid = (low + high) / 2;
      		if (getrange(a, l1, l1 + mid) == getrange(b, l2, l2 + mid)) low = mid;
      		else high = mid;
    	}
    	return low;
	}
  
  private:
    int n_;
    vector<ModInt61> power;
    ModInt61 base_;
};

int main() {
    int N,Q; cin >> N >> Q;
    string S,T; cin >> S >> T;
    vec<int> K(Q);
    vec<string> w(Q);
    int MAX = 0;
    rep(i,Q) {
        cin >> K[i];
        cin >> w[i];
        chmax(MAX,SZ(w[i]));
    }
    vector<SuffixArray<int>> SA;
    string str = S;
    rep(i,N+1) {
        SA.emplace_back();
        SA[i] = SuffixArray<int>(str);
        if (i==N or SZ(str) >= MAX) break;
        str = str + T[i] + str;
    }
 
    vvec<mint> table(N+1,vec<mint>(26));
    vec<mint> beki(N+1,1),bekiinv(N+1,1);
    rep(i,N) beki[i+1] = beki[i]*2;
    bekiinv[N] = beki[N].inv();
    rrep(i,N) bekiinv[i] = bekiinv[i+1]*2;
    
    {
        mint b = 1;
        rrep(i,N) {
            table[i+1][T[i]-'a'] = b;
            b *= 2;
        }
        rep(i,N) rep(j,26) {
            table[i+1][j] += table[i][j];
        }
    }
 
    auto base = RollingHash::generate_base();
    RollingHash RH(max(SZ(str),26),base);
    auto strhash = RH.get_hash(str);
    string abc = "";
    for (char c = 'a'; c <= 'z'; c++) abc += c;
    auto abchash = RH.get_hash(abc);
    
    rep(i,Q) {
        mint ans = 0;
        if (K[i] < SZ(SA)) {
            ans += SA[K[i]].count(w[i]);
            cout << ans << ln;
            continue;
        } 
 
        ans += beki[K[i]-(SZ(SA)-1)]*SA[SZ(SA)-1].count(w[i]);
        auto whash = RH.getval(w[i]);
        vec<int> cnt(26);
        for (int pre = 0; pre < SZ(w[i]); pre++) {
            int suf = SZ(w[i])-1-pre;
            auto prehash = RH.getrange(strhash,SZ(str)-pre,SZ(str));
            auto sufhash = RH.getrange(strhash,0,suf);
            rep(k,26) {
                auto chash = RH.getrange(abchash,k,k+1);
                auto subhash = RH.concat(RH.concat(prehash,chash,1),sufhash,suf);
                if (whash==subhash) cnt[k]++;    
            }
        }
        mint tmp = 0;
        rep(k,26) tmp += (table[K[i]][k] - table[SZ(SA)-1][k])*cnt[k];
        tmp *= bekiinv[N-K[i]];
        ans += tmp;
        cout << ans << ln;
    }
}