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.util.Random;

public class Main {

	public static void main(final String[] args) {
		new Main();
	}

	public Main() {
		final FastScanner fs = new FastScanner();
		final java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		solve(fs, out);
		out.flush();
	}

	public void solve(final FastScanner fs, final java.io.PrintWriter out) {
		final Random rnd = new Random();
		final int n = fs.nextInt(), q = fs.nextInt();
		final char[] s = fs.next().toCharArray(), t = fs.next().toCharArray();
		final long base = base(rnd);
		final Str[] str = new Str[n + 1];
		int max;
		final int MOD = 1_000_000_007;
		for (max = 0;max <= n;++ max) {
			str[max] = new Str(s, t, max, base);
			if (str[max].s2.length >= 1000000) break;
			if (max == n) break;
		}
		powB = new long[1000001];
		powB[0] = 1;
		for (int i = 0;i < powB.length - 1;++ i) powB[i + 1] = mul(powB[i], base);
		final int[][] powS = new int[26][n + 1];
		for (int i = 0;i < n;++ i) {
			for (int j = 0;j < 26;++ j) powS[j][i + 1] = powS[j][i] * 2 % MOD;
			powS[t[i] - 'a'][i + 1] = (powS[t[i] - 'a'][i + 1] + 1) % MOD;
		}

		for (int i = 0;i < q;++ i) {
			final int k = fs.nextInt();
			final char[] w = fs.next().toCharArray();
			long ans = 0;
			int check = max;
			while (check > 0 && str[check - 1].s2.length >= w.length) -- check;
			if (k < check || str[check].s2.length < w.length) {
				out.println(0);
				continue;
			}
			final long hash = hash(w, base);
			{
				final int len = str[check].s2.length - w.length + 1;
				for (int l = 0;l < len;++ l) if (str[check].hash(l, l + w.length) == hash) ++ ans;
				ans *= IntMath.pow(2, k - check, MOD);
				ans %= MOD;
			}
			{
				final long[] sum = new long[26];
				final long[] hash2 = new long[w.length + 1];
				for (int m = 0;m < w.length;++ m) hash2[m + 1] = mod(mul(hash2[m], base) + w[m]);
				for (int m = 0;m < w.length;++ m) {
					final int fLen = m, lLen = w.length - m - 1;
					final long first = hash2[fLen];
					final long last = mod(MASK + hash2[w.length] - mul(hash2[m + 1], powB[lLen]));
					if (str[check].hash(str[check].s2.length - fLen, str[check].s2.length) == first &&
						str[check].hash(0, lLen) == last) {
						++ sum[w[m] - 'a'];
					}
				}
				for (int c = 0;c < 26;++ c) {
					if (sum[c] != 0) {
						ans += sum[c] * powS[c][k] % MOD;
						ans += MOD - sum[c] * powS[c][check] % MOD * IntMath.pow(2, k - check, MOD) % MOD;
						ans %= MOD;
					}
				}
			}
			out.println(ans);
		}
	}
	static long[] powB;
	long hash(final char[] s, final long base) {
		long ret = 0;
		for (final char c : s) ret = mul(ret, base) + c;
		return mod(ret);
	}

	class Str {
		char[] s2;
		long[] hash;
		Str(final char[] s, final char[] t, final int m, final long base) {
			s2 = calc2(m, s, t);
			hash = new long[s2.length + 1];
			for (int i = 0;i < s2.length;++ i) hash[i + 1] = mod(mul(hash[i], base) + s2[i]);
		}
		long hash(final int l, final int r) {
			return mod(hash[r] - mul(hash[l], powB[r - l]) + MASK);
		}
	}
	static final long MASK = (1L << 61) - 1;
	static final long MASK0 = (1L << 30) - 1;
	static final long MASK1 = (1L << 31) - 1;

	long mul(final long a, final long b) {
		final long au = a >>> 31;
		final long ad = a & MASK1;
		final long bu = b >>> 31;
		final long bd = b & MASK1;
		final long mid =ad * bu +au * bd;
		final long midu = mid >>> 30;
		final long midd = mid & MASK0;
		return mod((au * bu << 1) + midu + (midd << 31) + ad * bd);
	}

	long mod(final long x) {
		final long xu = x >>> 61;
		final long xd = x & MASK;
		long res = xu + xd;
		if (res >= MASK) res -= MASK;
		return res;
	}

	long base(final Random rnd) {
		while(true) {
			long e = mod(rnd.nextLong());
			if (IntMath.gcd(e, MASK - 1) == 1) {
				long ans = 1;
				for (long mul = 37; e > 0; e >>= 1, mul = mul(mul, mul))
					if ((e & 1) != 0) ans = mul(ans, mul);
				return ans;
			}
		}
	}

	char[] calc2(final int m, final char[] s, final char[] t) {
		int len = s.length;
		for (int i = 0;i < m;++ i) len = len * 2 + 1;
		final char[] ret = new char[len];
		calc3(0, len, ret, s, t, m - 1);
		return ret;
	}

	void calc3(final int l, final int r, final char[] s2, final char[] s, final char[] t, final int n) {
		if (n < 0) {
			for (int i = 0;i < s.length;++ i) s2[i + l] = s[i];
			return;
		}
		s2[l + r >> 1] = t[n];
		calc3(l, l + r >> 1, s2, s, t, n - 1);
		calc3((l + r >> 1) + 1, r, s2, s, t, n - 1);
	}
}

class FastScanner {

	private final java.io.InputStream in = System.in;
	private final byte[] buffer = new byte[8192];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		ptr = 0;
		try {
			buflen = in.read(buffer);
		} catch (final java.io.IOException e) {
			e.printStackTrace();
		}
		return buflen > 0;
	}

	private byte readByte() {
		return hasNextByte() ? buffer[ptr++ ] : -1;
	}

	private static boolean isPrintableChar(final byte c) {
		return 32 < c || c < 0;
	}

	private static boolean isNumber(final int c) {
		return '0' <= c && c <= '9';
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++ ;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		final StringBuilder sb = new StringBuilder();
		byte b;
		while (isPrintableChar(b = readByte()))
			sb.appendCodePoint(b);
		return sb.toString();
	}

	public final char nextChar() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		return (char)readByte();
	}

	public final long nextLong() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		long n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte()))
					n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do
				n = n * 10 + b - '0';
			while (isNumber(b = readByte()));
		} catch (final java.util.NoSuchElementException e) {}
		return n;
	}

	public final int nextInt() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		int n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte()))
					n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do
				n = n * 10 + b - '0';
			while (isNumber(b = readByte()));
		} catch (final java.util.NoSuchElementException e) {}
		return n;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

class Arrays {

	public static void sort(final int[] array) {
		int l, min = 0xFFFFFFFF, max = 0;
		for (l = 0; l < array.length; ++l) {
			final int i = array[l];
			min &= i;
			max |= i;
			if ((i & 0x80000000) == 0) break;
		}
		for (int r = l + 1; r < array.length; ++r) {
			final int i = array[r];
			min &= i;
			max |= i;
			if ((i & 0x80000000) != 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		final int use = min ^ max, bit = Integer.highestOneBit(use & 0x7FFFFFFF);
		if (bit == 0) return;
		sort(array, 0, l, use, bit);
		sort(array, l, array.length, use, bit);
	}

	private static void sort(final int[] array, final int left, final int right, final int use, int digit) {
		if (right - left <= 96) {
			for (int i = left + 1; i < right; ++i) {
				final int tmp = array[i];
				int tmp2, j;
				for (j = i; j > left && (tmp2 = array[j - 1]) > tmp; --j)
					array[j] = tmp2;
				array[j] = tmp;
			}
			return;
		}
		int l = left;
		while (l < right && (array[l] & digit) == 0)
			++l;
		for (int r = l + 1; r < right; ++r) {
			final int i = array[r];
			if ((i & digit) == 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		if ((digit = Integer.highestOneBit(use & digit - 1)) == 0) return;
		sort(array, left, l, use, digit);
		sort(array, l, right, use, digit);
	}

	public static void sort(final long[] array) {
		int l;
		long min = 0xFFFFFFFFFFFFFFFFL, max = 0;
		for (l = 0; l < array.length; ++l) {
			final long i = array[l];
			min &= i;
			max |= i;
			if ((i & 0x8000000000000000L) == 0) break;
		}
		for (int r = l + 1; r < array.length; ++r) {
			final long i = array[r];
			min &= i;
			max |= i;
			if ((i & 0x8000000000000000L) != 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		final long use = min ^ max, bit = Long.highestOneBit(use & 0x7FFFFFFFFFFFFFFFL);
		if (bit == 0) return;
		sort(array, 0, l, use, bit);
		sort(array, l, array.length, use, bit);
	}

	private static void sort(final long[] array, final int left, final int right, final long use, long digit) {
		if (right - left <= 96) {
			for (int i = left + 1, j; i < right; ++i) {
				final long tmp = array[i];
				long tmp2;
				for (j = i; j > left && (tmp2 = array[j - 1]) > tmp; --j)
					array[j] = tmp2;
				array[j] = tmp;
			}
			return;
		}
		int l = left;
		while (l < right && (array[l] & digit) == 0)
			++l;
		for (int r = l + 1; r < right; ++r) {
			final long i = array[r];
			if ((i & digit) == 0) {
				array[r] = array[l];
				array[l++ ] = i;
			}
		}
		if ((digit = Long.highestOneBit(use & digit - 1)) == 0) return;
		sort(array, left, l, use, digit);
		sort(array, l, right, use, digit);
	}
}

class IntMath {

	public static int gcd(int a, int b) {
		while (a != 0)
			if ((b %= a) != 0) a %= b;
			else return a;
		return b;
	}

	public static int gcd(final int... array) {
		int ret = array[0];
		for (int i = 1; i < array.length; ++i)
			ret = gcd(ret, array[i]);
		return ret;
	}

	public static long gcd(long a, long b) {
		while (a != 0)
			if ((b %= a) != 0) a %= b;
			else return a;
		return b;
	}

	public static long gcd(final long... array) {
		long ret = array[0];
		for (int i = 1; i < array.length; ++i)
			ret = gcd(ret, array[i]);
		return ret;
	}

	public static long lcm(final long a, final long b) {
		return a / gcd(a, b) * b;
	}

	public static int pow(final int a, int b) {
		int ans = 1;
		for (int mul = a; b > 0; b >>= 1, mul *= mul)
			if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static long powLong(final long a, long b) {
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul *= mul)
			if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static int pow(final int a, int b, final int mod) {
		if (b < 0) b = b % (mod - 1) + mod - 1;
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod)
			if ((b & 1) != 0) ans = ans * mul % mod;
		return (int)ans;
	}

	public static int floorsqrt(final long n) {
		return (int)Math.sqrt(n + 0.1);
	}

	public static int ceilsqrt(final long n) {
		return n <= 1 ? (int)n : (int)Math.sqrt(n - 0.1) + 1;
	}
}