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;

#ifdef DEBUG
#include "../../debug.h"
#else
#define DEB(...)
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define sz(a) ((int)(a).size())
#define forn(i,n) for(int i=0; i<(n); i++)
#define forne(i,n) for(int i=0; i<(n) || (cout << endl,0) ; i++) 
#define fora(i,a,b) for(int i=a; i<=(b); i++)
#define ford(i,a,b) for(int i=a; i>=(b); i--)
#define muniq(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template<class T> bool mmin(T& a, const T& b) { return b<a?a=b,1:0; }
template<class T> bool mmax(T& a, const T& b) { return a<b?a=b,1:0; }
template<class T> void puts(T a) { cout << a << ' '; }
template<class T> void put(T a) { cout << a << endl; }
template<class T> void put(T ita, T itb) { while(ita!=itb) puts(*ita++); cout << endl; }
void yesno(bool c) { put(c?"YES":"NO"); }
void yes() { yesno(true); } void no() { yesno(false); }
void imp() { put("-1"); }
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

// -------------------------------------
template <int m>    // m must be prime
struct modint {
  public:
    static constexpr int mod() { return m; }

    modint() : _v(0) {}

    template <class T>
    modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    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/=(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 {
        assert(0 <= n);
        modint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    modint inv() const {
        assert(_v);
        return pow(umod() - 2);
    }

    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 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 bool operator<(const modint& lhs, const modint& rhs) {
        return lhs._v < rhs._v;
    }
    friend string to_string(const modint& rhs) {
        return to_string(rhs.val());
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& a) {
        os << to_string(a);
        return os;
    }
    
  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
};
using mint = modint<1000000007>;
//using mintb = modint<998244353>;
// -------------------------------------
// -----------------------------------------------
struct mod_consts {
    static const int a = 989910403; 
    static const int b = 995462137; 
    static const int c = 979797979;     
};

template<int... args>
struct base_hash {
    static const array<int,sizeof...(args)> md;
    array<int,sizeof...(args)> h;

    friend bool operator == (const base_hash& lhs, const base_hash& rhs) {
        return lhs.h == rhs.h;
    }

    friend bool operator < (const base_hash& lhs, const base_hash& rhs) {
        for(int i=0; i<(int)md.size(); i++) {
            if(lhs.h[i]!=rhs.h[i]) return lhs.h[i] < rhs.h[i];
        }
        return 0;
    }
};
template<int... args> const array<int,sizeof...(args)> base_hash<args...>::md = {args...};
// -----------------------------------------------

// -----------------------------------------------
// also include: base_hash
template<int... args>
struct hhash : base_hash<args...> {
    using base_hash<args...>::md;
    using base_hash<args...>::h;

    hhash() : hhash(0) {}
    hhash(long long x) : hhash({(args,x)...}) {}
    hhash(array<long long,sizeof...(args)> v) {
        for(int i=0; i<(int)md.size(); i++) 
            h[i] = (v[i]%md[i] + md[i])%md[i];
    }

    hhash& operator*= (const hhash& rhs) {
        for(int i=0; i<(int)md.size(); i++) 
            h[i] = (1LL * h[i] * rhs.h[i]) % md[i];
        return *this;
    }
    
    hhash& operator+= (const hhash& rhs) {
        for(int i=0; i<(int)md.size(); i++) 
            h[i] = (h[i] + rhs.h[i]) % md[i];
        return *this;
    }

    hhash pow(long long n) const {
        assert(0 <= n);
        hhash x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    friend hhash operator * (const hhash& lhs, const hhash& rhs) {
        return hhash(lhs) *= rhs;
    }
    
    friend hhash operator + (const hhash& lhs, const hhash& rhs) {
        return hhash(lhs) += rhs;
    }
};

// in order to use hhash as key in an unordered_map
template <int... args>
struct hash<hhash<args...>> {            
    size_t operator()(const hhash<args...>& a) const {
        size_t ans = 0;
        for(int val : a.h)  ans = (ans ^ (hash<int>()(val) << 1)) >> 1;
        for(int val : a.md) ans = (ans ^ (hash<int>()(val) << 1)) >> 1;
        return ans;
    }
};
using hh = hhash<mod_consts::a,mod_consts::b>;
// -----------------------------------------------

// -----------------------------------------------
// for string hashing, also include: base_hash, hhash
template<class T>
struct shash {
    int len = 0;
    T hash;
    static T pr;

    shash() : shash(string()) {}
    shash(const char c) : shash(string(1,c)) {}
    shash(const string& s) {
        len = s.length();
        hash = stohash(s);
    }

    shash& operator+= (const shash& rhs) {
        len += rhs.len;
        hash *= pr.pow(rhs.len);
        hash += rhs.hash;
        return *this;
    }

    friend shash operator+ (const shash& lhs, const shash& rhs) {
        return shash(lhs) += rhs;
    }

    friend bool operator == (const shash& lhs, const shash& rhs) {
        return lhs.len == rhs.len && lhs.hash == rhs.hash;
    }

  private:
    T stohash(const string& s){
        T ans(s[0]);
        for(int i=1; i<(int)s.length(); i++) {
            ans = ans*pr + T(s[i]);
        }
        return ans;
    }
};
template<class T> T shash<T>::pr = 257;

// in order to use shash as key in an unordered_map
template <class T>
struct hash<shash<T>> {            
    size_t operator()(const shash<T>& a) const {
        size_t ans = hash<T>()(a.hash);
        ans = (ans ^ (hash<int>()(a.len) << 1)) >> 1;
        return ans;
    }
};

const int pra = 10007;
const int prb = 5153;
const int prc = 7001;
template<> hh shash<hh>::pr = hh({pra,prb});
using ss = shash<hh>;
// -----------------------------------------------


vector<int> prefix_function(string &s) 
{
    int n = s.size();
    vector<int> pi(n);
    for(int i = 1; i < n; i++) 
    {
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

vector<int> find_occurences(string &text, string &pattern)
{
    string cur = pattern + '#' + text;
    int sz1 = text.size(), sz2 = pattern.size();
    vector<int> v;
    vector<int> lps = prefix_function(cur);
    for(int i = sz2 + 1; i <= sz1 + sz2; i++)
    {
        if(lps[i] == sz2)
            v.push_back(i - 2 * sz2);
    }
    return v;
}

// ans[i]: shash of s[0..i]
vector<ss> leftshash(const string& s) {
    int n = s.length();
    vector<ss> ans(n);
    ans[0] = s[0];
    for(int i = 1; i < n; i++) {
        ans[i] = ans[i-1] + s[i];
    }
    return ans;
}

// ans[i]: shash of s[i..(s.length()-1)]
vector<ss> rightshash(const string& s) {
    int n = s.length();
    vector<ss> ans(n);
    ans[n-1] = s[n-1];
    for(int i = n - 2; i >= 0; i--) {
        ans[i] = s[i] + ans[i+1];
    }
    return ans;
}


void solve() {

    int n,q; 
    cin >> n >> q;

    vector<string> s(n+1);
    string t;
    cin >> s[0] >> t;

    fora(i,1,n) {
        s[i] = s[i-1] + t[i-1] + s[i-1];
        if(s[i].length()>1000100) break;
    }

    vector<mint> pow(n+1);
    pow[0] = 1;
    fora(i,1,n) pow[i] = pow[i-1] * 2;

    vector<vector<mint>> let(26,vector<mint>(n+2));
    fora(i,1,n) {
        forn(c,26) let[c][i] = let[c][i-1] * 2;
        let[t[i-1]-'a'][i]++;
    }

    vector<vector<ss>> rsh(min(21,n+1));// = rightshash(s[it]);
    vector<vector<ss>> lsh(min(21,n+1));// = leftshash(s[it]);
//    for(int it=0; it<=n; it++) {
////        DEB(s[it].length());
//        if(s[it].length()>1000101) break;
//        rsh[it] = rightshash(s[it]);
//        lsh[it] = leftshash(s[it]);
//    }

    vi x(q);
    vector<string> p(q);
    forn(qq,q) cin >> x[qq] >> p[qq];

    vector<mint> ans(q);
    vi nomore(q), pos(q);

    forn(qq,q) {
        int xx = x[qq];
        string pp = p[qq];

        bool found = false;
        forn(i,n+1) {
            if(i>xx) break;
            if(s[i].length()>=pp.length()) {
                vi occ = find_occurences(s[i],pp);
                ans[qq] = mint(occ.size()) * pow[xx-i];
                pos[qq] = i;
                found = true;
                if(i==xx) nomore[qq] = 1;
                break;
            }
        }
        if(!found) {
            ans[qq] = 0;
            nomore[qq] = 1;
        }
    }

    forn(qq,q) {
        if(!nomore[qq]) {
            if(rsh[pos[qq]].empty()) {
                rsh[pos[qq]] = rightshash(s[pos[qq]]);
                lsh[pos[qq]] = leftshash(s[pos[qq]]);
            }
        }
    }

    forn(qq,q) {
        if(!nomore[qq])  {
            int xx = x[qq], it = pos[qq];
            string pp = p[qq];

            if(xx>it) {
                vector<ss> rph = rightshash(pp);
                vector<ss> lph = leftshash(pp);

                int plen = pp.length(), slen = s[it].length();

                vi lcnt(26);
                forn(i,plen) {
                    int ok = 1;
                    if(i>0) ok = ok && (rsh[it][slen-i] == lph[i-1]);
                    if(i<plen-1) ok = ok && (lsh[it][plen-2-i] == rph[i+1]);
                    if(ok) lcnt[pp[i]-'a']++;
                }

                forn(c,26) {
                    ans[qq] += lcnt[c] * (let[c][xx]-let[c][it]*pow[xx-it]);
                }
            }
        }
        put(ans[qq]);
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 1; //cin >> tc;
    while(tc--) solve();

    return 0;
}