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 JAVA):

Solution:
/**
 * author: derrick20
 * created: 12/30/20 11:56 AM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class SongOfSirens {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = sc.nextInt();
        int Q = sc.nextInt();
        String s = sc.next();
        String t = "_".concat(sc.next());
        int len = s.length();
        int steps = 0;
        // key bug 2, it IS 10^6
        while (len < 1000000) { // key bug always using 21 steps can go a bit too high
            len = 2 * len + 1;
            steps++;
        }
        char[][] table = new char[min(N, steps) + 1][]; // len less than 10^6, so 2^21 covers it
        // L(n) = 2L(n - 1) + 1
        table[0] = s.toCharArray();
        for (int i = 1; i < table.length; i++) {
            table[i] = (new String(table[i - 1]) + t.charAt(i) + new String(table[i - 1])).toCharArray();
//            System.out.println(new String(table[i]));
        }
        int MAXLEN = table[table.length - 1].length;
        basePow = new long[MAXLEN + 1]; // key bug: k can still go beyond the table length
        baseInvPow = new long[MAXLEN + 1];
        long[] twoPow = new long[MAXLEN+ 1];
        basePow[0] = baseInvPow[0] = twoPow[0] = 1;
        for (int i = 1; i < basePow.length; i++) {
            basePow[i] = base * basePow[i - 1] % mod;
            baseInvPow[i] = baseInv * baseInvPow[i - 1] % mod;
            twoPow[i] = 2 * twoPow[i - 1] % mod;
        }

        long[][] growthPrefix = new long[26][t.length()];
        long[] currDelta = new long[26];
        for (int i = 1; i < t.length(); i++) {
            long[] nextDelta = new long[26];
            for (int c = 0; c < 26; c++) {
                nextDelta[c] = 2 * currDelta[c] % mod;
                growthPrefix[c][i] = add(growthPrefix[c][i - 1], currDelta[c]);
                if (t.charAt(i) -'a' == c) {
                    growthPrefix[c][i] = add(growthPrefix[c][i], 1);
                    nextDelta[c] = add(nextDelta[c], 1);
                }
            }
            currDelta = nextDelta;
        }
//        for (char c = 'a'; c <= 'd'; c++) {
//            System.out.println("Growth of " + c + " = " + Arrays.toString(growthPrefix[c - 'a']));
//        }
        while (Q-->0) {
            int k = sc.nextInt();
            char[] sailor = sc.next().toCharArray();
            int n = sailor.length;
            int last = 0;
            while (last < table.length && sailor.length > table[last].length) {
                last++;
            }
            ASSERT(last < table.length); // last length is > 10^6
            if (last > k) {
                out.println(0);
            } else {
                // need to check from last to kth iteration
                Hash sailorHash = new Hash(sailor);
                Hash songHash = new Hash(table[last]);
//                System.out.println("Last song = " + new String(table[last]));
//                System.out.println("Sailor = " + new String(sailor));
                int m = table[last].length;
                long intraMatches = 0;
                for (int i = 1; i <= m - n + 1; i++) {
                    if (sailorHash.hash == songHash.queryRange(i, i + n - 1)) {
                        intraMatches++;
                    }
                }
//                System.out.println("intramatches for one song = " + intraMatches);
                intraMatches = (intraMatches * twoPow[k - last]) % mod;
                int[] bridgeWays = new int[26];
                for (int front = 0; front <= n - 1; front++) {
                    // front can be empty potentially, still "spans" it
                    int back = n - 1 - front;
                    if (sailorHash.queryRange(1, front) == songHash.queryRange(m - front + 1, m) && sailorHash.queryRange(front + 2, n) == songHash.queryRange(1, back)) {
                        bridgeWays[sailor[front] - 'a']++; // index = (front - 1) + 1 (we want the front + 1 char)
                    }
                }
//                System.out.println("Ways for each bridge = " + Arrays.toString(bridgeWays));
                long interMatches = 0;
                for (int c = 0; c < 26; c++) {
                    long prevGrowth = (twoPow[k - last] * growthPrefix[c][last]) % mod;
                    long accumulated = sub(growthPrefix[c][k], prevGrowth); // each iteration after last adds some amount
                    long matches = bridgeWays[c] * accumulated % mod;
                    interMatches = add(interMatches, matches);
                }
//                System.out.println("Intermatches = " + interMatches);
                long ans = add(intraMatches, interMatches);
//                System.out.println("-------------------------------");
                out.println(ans);
            }
//            for (int i = 0; i < table.length; i++) {
//                int[] longestMatch = KMP(table[i].toCharArray(), sailor.toCharArray());
//                System.out.println(Arrays.toString(longestMatch));
//            }
        }
        out.close();
    }
/*
4 1
aba
bbac
3 ab
 */
    static long mod = (long) 1e9 + 7;
    static long base = 29, baseInv = fastExpo(base, mod - 2);
    static long[] basePow, baseInvPow;

    static long add(long a, long b) {
        long ans = a + b;
        if (ans >= mod) {
            ans -= mod;
        }
        return ans;
    }

    static long sub(long a, long b) {
        long ans = a - b;
        if (ans < 0) {
            ans += mod;
        }
        return ans;
    }

    static class Hash {
        char[] s;
        long[] prefixHash;
        long hash;
        int n;
        public Hash(char[] s) {
            n = s.length;
            this.s = s;
            prefixHash = new long[n + 1];
            prefixHash[1] = s[0] - 'a' + 1; // KEY BUG: don't want ab = ba, need a > 0!!!
            for (int i = 2; i <= n; i++) {
                long digit = basePow[i - 1] * (s[i - 1] - 'a' + 1) % mod; // grows triangularly to the right
                prefixHash[i] = (prefixHash[i - 1] + digit) % mod;
            }
            hash = prefixHash[n];
        }

        // get 1-indexed range
        public long queryRange(int l, int r) {
            long ans = (prefixHash[r] - prefixHash[l - 1] + mod) % mod;
            ans = (ans * baseInvPow[l - 1]) % mod; // index l has a power of b^(l - 1)
            return ans;
        }
    }

    static long fastExpo(long x, long k) {
        long ans = 1;
        for (; k > 0; k >>= 1, x = (x * x) % mod) {
            if ((k & 1) > 0) {
                ans = x * ans % mod;
            }
        }
        return ans;
    }

    static int[] KMP(char[] S, char[] T) {
        // want to find a match of T in S ending at each suffix
        // 0-indexed
        char[] P = new char[T.length + 1 + S.length];
        for (int i = 0; i < T.length; i++) {
            P[i] = T[i];
        }
        P[T.length] = '#';
        for (int j = T.length + 1, ix = 0; j < P.length; j++, ix++) {
            P[j] = S[ix];
        }
        int[] prefixLength = new int[P.length];
        for (int j = 1; j < P.length; j++) {
            int i = prefixLength[j - 1];
            while (i > 0 && P[i] != P[j]) {
                i = prefixLength[i - 1];
            }
            if (P[i] == P[j]) {
                i++;
            }
            prefixLength[j] = i;
        }
        int[] longestMatch = new int[S.length];
        for (int i = T.length + 1, ix = 0; i < P.length; i++, ix++) {
            longestMatch[ix] = prefixLength[i];
        }
        return longestMatch;
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
    
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
    
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
    
        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
    
        int nextInt() {
            return (int) nextLong();
        }
    
        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
    
        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }
    
        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}