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.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
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) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            GSongOfTheSirens solver = new GSongOfTheSirens();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class GSongOfTheSirens {
        int mod = (int) 1e9 + 7;
        char[] buf = new char[(int) 3e6];
        int[] topology;
        int[] tag;
        AhoCorasick ac;
        int[] pow2;
        int[] inv2;

        {
            pow2 = new int[(int) 1e6];
            inv2 = new int[(int) 1e6];
            pow2[0] = 1;
            inv2[0] = 1;
            int inv = (mod + 1) / 2;
            for (int i = 1; i < 1e6; i++) {
                pow2[i] = (int) ((long) pow2[i - 1] * 2 % mod);
                inv2[i] = (int) ((long) inv2[i - 1] * inv % mod);
            }
        }

        public void pushUp() {
            for (int i = topology.length - 1; i >= 1; i--) {
                int node = topology[i];
                int p = ac.fails[node];
                tag[p] += tag[node];
                if (tag[p] < 0) {
                    tag[p] += mod;
                } else if (tag[p] >= mod) {
                    tag[p] -= mod;
                }
            }
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int q = in.ri();
            ac = new AhoCorasick('a', 'z', (int) 1e6);
            char[] s0 = in.rs().toCharArray();
            char[] t = new char[n + 1];
            in.rs(t, 1);
            Query[] qs = new Query[q];
            int limit = (int) 1e6;
            for (int i = 0; i < q; i++) {
                qs[i] = new Query();
                qs[i].k = in.ri();
                int m = in.rs(buf, 0);
                ac.prepareBuild();
                for (int j = 0; j < m; j++) {
                    ac.build(buf[j]);
                }
                qs[i].node = ac.buildLast;
            }
            topology = ac.endBuild();
            tag = new int[topology.length];
            int len;
            {
                System.arraycopy(s0, 0, buf, 0, s0.length);
                len = s0.length;
                ac.prepareMatch();
                Arrays.fill(tag, 0);
                for (int j = 0; j < len; j++) {
                    ac.match(buf[j]);
                    tag[ac.matchLast]++;
                }

                pushUp();
                for (Query query : qs) {
                    query.ans += (long) tag[query.node] * pow2[query.k] % mod;
                }
            }

            int prevLen = -1;
            int now = 1;
            for (; now <= n && len <= limit; now++) {
                prevLen = len;
                buf[prevLen] = t[now];
                len = len * 2 + 1;
                for (int j = 0; j < prevLen; j++) {
                    buf[j + prevLen + 1] = buf[j];
                }

                ac.prepareMatch();
                Arrays.fill(tag, 0);
                for (int j = 0; j < prevLen; j++) {
                    ac.match(buf[j]);
                    tag[ac.matchLast]--;
                }
                for (int j = prevLen; j < len; j++) {
                    ac.match(buf[j]);
                    tag[ac.matchLast]++;
                }

                pushUp();
                for (Query query : qs) {
                    if (query.k >= now) {
                        query.ans += (long) tag[query.node] * pow2[query.k - now] % mod;
                    }
                }
            }

            long[] ps = new long[n + 1];
            for (int c = 'a'; c <= 'z'; c++) {
                Arrays.fill(ps, 0);
                for (int j = now; j <= n; j++) {
                    if (t[j] == c) {
                        ps[j] = inv2[j];
                    }
                }
                for (int i = 1; i <= n; i++) {
                    ps[i] += ps[i - 1];
                    if (ps[i] >= mod) {
                        ps[i] -= mod;
                    }
                }
                buf[prevLen] = (char) c;
                ac.prepareMatch();
                Arrays.fill(tag, 0);
                for (int j = 0; j < prevLen; j++) {
                    ac.match(buf[j]);
                    tag[ac.matchLast]--;
                }
                for (int j = prevLen; j < len; j++) {
                    ac.match(buf[j]);
                    tag[ac.matchLast]++;
                }

                pushUp();
                for (Query query : qs) {
                    if (query.k >= now) {
                        query.ans += ps[query.k] * pow2[query.k] % mod *
                                tag[query.node] % mod;
                    }
                }
            }

            for (Query query : qs) {
                int ans = DigitUtils.mod(query.ans, mod);
                out.println(ans);
            }
        }

    }

    static class AhoCorasick {
        public int[][] next;
        public int[] fails;
        private int minChar;
        private int maxChar;
        private int allocIndicator;
        private int range;
        public int buildLast;
        public int matchLast;

        public void init() {
            allocIndicator = 1;
        }

        private int alloc() {
            return allocIndicator++;
        }

        public AhoCorasick(int minChar, int maxChar, int cap) {
            this.minChar = minChar;
            this.maxChar = maxChar;
            range = maxChar - minChar + 1;
            next = new int[range][cap + 1];
            fails = new int[cap + 1];
            init();
        }

        public void prepareBuild() {
            buildLast = 0;
        }

        public void prepareMatch() {
            matchLast = 0;
        }

        public void build(int c) {
            c -= minChar;
            if (next[c][buildLast] == 0) {
                next[c][buildLast] = alloc();
            }
            buildLast = next[c][buildLast];
        }

        public void match(int c) {
            c -= minChar;
            matchLast = next[c][matchLast];
        }

        public int[] endBuild() {
            int[] dq = new int[allocIndicator];
            int dqTail = 1;
            int dqHead = 1;
            fails[0] = -1;
            for (int i = 0; i < range; i++) {
                if (next[i][0] != 0) {
                    dq[dqTail++] = next[i][0];
                    fails[next[i][0]] = 0;
                }
            }

            while (dqHead < dqTail) {
                int head = dq[dqHead++];
                for (int i = 0; i < range; i++) {
                    if (next[i][head] != 0) {
                        dq[dqTail++] = next[i][head];
                        int fail = visit(fails[head], i);
                        if (fail == -1) {
                            fail = 0;
                        } else {
                            fail = next[i][fail];
                        }
                        fails[next[i][head]] = fail;
                    }
                }
            }

            dqTail = 1;
            dqHead = 1;
            for (int i = 0; i < range; i++) {
                if (next[i][0] != 0) {
                    dq[dqTail++] = next[i][0];
                }
            }
            while (dqHead < dqTail) {
                int head = dq[dqHead++];
                for (int i = 0; i < range; i++) {
                    if (next[i][head] != 0) {
                        dq[dqTail++] = next[i][head];
                    } else {
                        next[i][head] = next[i][fails[head]];
                    }
                }
            }

            assert dqTail == allocIndicator;
            return dq;
        }

        public int visit(int trace, int index) {
            while (trace != -1 && next[index][trace] == 0) {
                trace = fails[trace];
            }
            return trace;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int mod(long x, int mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return (int) x;
        }

    }

    static class Query {
        int k;
        int node;
        long ans;

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int rs(char[] data, int offset) {
            return readString(data, offset);
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}