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:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskG solver = new TaskG();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskG {
        static final int MOD = 1000000007;
        static final int MAXN = 110000;
        int[] P;
        int[] IP;
        int[][] F;

        int add(int a, int b) {
            a += b;
            if (a >= MOD) a -= MOD;
            return a;
        }

        public static int[] zFunction(String s) {
            int[] z = new int[s.length()];
            for (int i = 1, l = 0, r = 0; i < z.length; ++i) {
                if (i <= r)
                    z[i] = Math.min(r - i + 1, z[i - l]);
                while (i + z[i] < z.length && s.charAt(z[i]) == s.charAt(i + z[i])) ++z[i];
                if (r < i + z[i] - 1) {
                    l = i;
                    r = i + z[i] - 1;
                }
            }
            return z;
        }

        int getWays(char[] t, int depth, int max_depth, char[] w) {
            int L = w.length;
            if (L == 0) return P[max_depth - depth];
            if (depth == max_depth) return 0;
            if (L == 1) {
                int p = w[0] - 'a';
                int A = max_depth == 0 ? 0 : F[max_depth - 1][p];
                int B = depth == 0 ? 0 : F[depth - 1][p];
                A -= B;
                if (A < 0) A += MOD;
                return (int) ((A * 1L * P[max_depth]) % MOD);
            }
            boolean[] at = new boolean[2];
            at[0] = at[1] = true;
            for (int i = 0; i < L; i++) {
                at[i & 1] &= w[i] == t[depth];
            }
            int ans = 0;
            int l1 = L / 2, l0 = L - l1;
            int store = -1;
            if (at[0]) {
                char[] w0 = new char[l1];
                int pos = 0;
                for (int i = 1; i < L; i += 2) w0[pos++] = w[i];
                ans = store = getWays(t, depth + 1, max_depth, w0);
            }
            if (at[1]) {
                char[] w1 = new char[l0];
                int pos = 0;
                for (int i = 0; i < L; i += 2) w1[pos++] = w[i];
                if (l0 == l1 && store != -1) ans = add(ans, store);
                else ans = add(ans, getWays(t, depth + 1, max_depth, w1));
            }
            return ans;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            P = new int[MAXN];
            IP = new int[MAXN];
            F = new int[MAXN][26];
            P[0] = IP[0] = 1;

            for (int i = 1; i < MAXN; i++) {
                P[i] = (P[i - 1] * 2) % MOD;
                IP[i] = (int) ((IP[i - 1] * 1L * ((MOD + 1) / 2)) % MOD);
            }

            int n = in.nextInt(), q = in.nextInt();
            String s0 = in.next();
            String t = in.next();

            for (int i = 0; i < n; i++) {
                if (i != 0) F[i] = F[i - 1].clone();
                F[i][t.charAt(i) - 'a'] = add(F[i][t.charAt(i) - 'a'], IP[i + 1]);
            }
            char[] T = t.toCharArray();
            for (int qq = 0; qq < q; qq++) {
                int k = in.nextInt();
                String w = in.next();
                int[] z1 = zFunction(s0 + "$" + w);
                int[] z2 = zFunction(w + "$" + s0);
                int ls = s0.length(), lw = w.length();
                int result = 0;
                for (int i = 0; i <= ls; i++) {
                    int l = ls - i;
                    if (l > 0 && z2[lw + 1 + i] < Integer.min(lw, l)) continue;
                    char[] seq = new char[lw <= l ? 0 : 1 + (lw - l - 1) / (ls + 1)];
                    boolean possible = true;
                    int pos = 0;
                    if (l < lw) seq[pos++] = w.charAt(l);
                    for (int j = l + 1; j < lw; j += ls + 1) {
                        int min_lcp = Integer.min(ls, lw - j);
                        if (z1[ls + 1 + j] < min_lcp) {
                            possible = false;
                            break;
                        }
                        if (j + ls < lw) seq[pos++] = w.charAt(j + ls);
                    }

                    if (possible) {
                        result = add(result, getWays(T, 0, k, seq));
                    }
                }
                out.println(result);
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void println(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
            writer.print('\n');
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}