#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 1000000007
#define inf 1000000000000000000LL
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;

#define endl '\n'
#define int long long

void computeLPSArray(char* pat, int M, int* lps); 
  
// Prints occurrences of txt[] in pat[] 
void KMPSearch(char* pat, char* txt, int mm, vector<int> &match) 
{ 
    int M = strlen(pat); 
    int N = strlen(txt); 
  
    // create lps[] that will hold the longest prefix suffix 
    // values for pattern 
    int lps[M]; 
  
    // Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps); 
  
    int i = 0; // index for txt[] 
    int j = 0; // index for pat[] 
    while (i < N) { 
        if (pat[j] == txt[i]) { 
            j++; 
            i++; 
        } 
  
        if (j == M) { 
            match[(i-j-1+mm)%mm]++;
            j = lps[j - 1]; 
        } 
  
        // mismatch after j matches 
        else if (i < N && pat[j] != txt[i]) { 
            // Do not match lps[0..lps[j-1]] characters, 
            // they will match anyway 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        } 
    } 
} 
  
// Fills lps[] for given patttern pat[0..M-1] 
void computeLPSArray(char* pat, int M, int* lps) 
{ 
    // length of the previous longest prefix suffix 
    int len = 0; 
  
    lps[0] = 0; // lps[0] is always 0 
  
    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else // (pat[i] != pat[len]) 
        { 
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1]; 
  
                // Also, note that we do not increment 
                // i here 
            } 
            else // if (len == 0) 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
} 

string s,t;
int num;

int dp[100001][26];
int p2[1000001];

int solve(string &s, int index) {

	if(s.size()==0) {
		int ans = p2[num-index];
		return ans;
	}

	if(index==num) {
		return 0;
	}

	if(s.size()==1) {
		int ans = dp[num][s[0]-'a'];
		ans -= dp[index][s[0]-'a'];

		ans *= power(2, num);

		ans %= MOD;
		ans += MOD;
		ans %= MOD;

		return ans;
	}

	string str1 = "";
	string str2 = "";

	for(int i=0;i<s.size();i++) {
		if(i%2==0) str1 += s[i];
		else str2 += s[i];
	}

	int f1 = 1;
	int f2 = 1;

	for(int i=0;i<s.size();i++) {
		if(i%2==0) {
			if(s[i]!=t[index]) f1 = 0;
		}
		else {
			if(s[i]!=t[index]) f2 = 0;
		}
	}

	int ans = 0;

	if(f2) ans += solve(str1, index+1);
	if(f1) ans += solve(str2, index+1);

	ans %= MOD;

	// cout<<"#"<<s<<" "<<index<<" -- "<<ans<<endl;
	return ans;
}

signed main() {
	
	fast;

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

	cin>>s>>t;

	char* s1 = new char[s.size()+1];
	strcpy(s1, s.c_str());

	for(int i=1;i<=n;i++) {
		for(int j=0;j<26;j++) {
			dp[i][j] = dp[i-1][j];
		}
		dp[i][t[i-1]-'a'] = (dp[i][t[i-1]-'a']+power(2, (MOD-1)-(i)))%MOD;
	}

	p2[0] = 1;
	for(int i=1;i<=1000000;i++) p2[i] = (p2[i-1]*2)%MOD;

	while(q--) {

		int len = s.size();

		string str;

		cin>>num;
		cin>>str;

		vector<int> match(len+1,0);

		int ans = 0;

		char* strC = new char[str.size()+1];

		strcpy(strC, str.c_str());
		KMPSearch(s1, strC, len+1, match);

		unordered_map<string,int> cnt;

		for(int i=0;i<=len;i++) {
			// cout<<"$"<<i<<endl;
			int n = str.size();
			bool f = 1;
			string str1 = "";
			for(int j=0;j<min(i,n);j++) {
				if(str[j]!=s[len-(i-j)]) {
					// cout<<"##"<<j<<" "<<len<<"-("<<i<<"-"<<j<<")"<<str[j]<<" "<<s[len-(i-j)]<<endl;
					f = 0;
				}
			}

			if(!f) continue;

			int cur = 0;
			
			int mn = i;

			if(!f) continue;

			int j = i+(n/(len + 1) + 1)*(len+1);
			while(j-(len+1)>=n) j -= len + 1;

			if(j-(len+1)<n && j-(len+1)+1>=0) {
				int cur = 0;
				// cout<<""
				for(int k=j-(len+1)+1;k<n;k++) {
					if(str[k]!=s[cur]) {
						// cout<<"$"<<i<<j-(len+1)+1<<endl;
						f=0;break;
					}
					cur++;
				}
			}

			while(j+(len+1)>n) j -= (len+1);

			int cc = (j-i)/(len+1) + 1;
			if(i==len) cc++;
			cc = max(0LL, cc);

			// cout<<"#"<<i<<" -- "<<match[i]<<" "<<cc<<endl;

			if(match[i]!=cc) f = 0;

			if(f) {
				for(int j=i;j<n;j+=(len+1)) str1 += str[j];
				cnt[str1]++;
			// cout<<"$"<<i<<" -- "<<str1<<endl;
			}
		}

		for(auto &x: cnt) {
			string s = string(x.f);
			ans += x.s*solve(s, 0)%MOD;
			ans %= MOD;
		}

		cout<<ans<<endl;
	}
}
### Prompt

Generate a cpp solution to the following 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

### Response

```cpp
#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 1000000007
#define inf 1000000000000000000LL
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;

#define endl '\n'
#define int long long

void computeLPSArray(char* pat, int M, int* lps); 
  
// Prints occurrences of txt[] in pat[] 
void KMPSearch(char* pat, char* txt, int mm, vector<int> &match) 
{ 
    int M = strlen(pat); 
    int N = strlen(txt); 
  
    // create lps[] that will hold the longest prefix suffix 
    // values for pattern 
    int lps[M]; 
  
    // Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps); 
  
    int i = 0; // index for txt[] 
    int j = 0; // index for pat[] 
    while (i < N) { 
        if (pat[j] == txt[i]) { 
            j++; 
            i++; 
        } 
  
        if (j == M) { 
            match[(i-j-1+mm)%mm]++;
            j = lps[j - 1]; 
        } 
  
        // mismatch after j matches 
        else if (i < N && pat[j] != txt[i]) { 
            // Do not match lps[0..lps[j-1]] characters, 
            // they will match anyway 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        } 
    } 
} 
  
// Fills lps[] for given patttern pat[0..M-1] 
void computeLPSArray(char* pat, int M, int* lps) 
{ 
    // length of the previous longest prefix suffix 
    int len = 0; 
  
    lps[0] = 0; // lps[0] is always 0 
  
    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else // (pat[i] != pat[len]) 
        { 
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1]; 
  
                // Also, note that we do not increment 
                // i here 
            } 
            else // if (len == 0) 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
} 

string s,t;
int num;

int dp[100001][26];
int p2[1000001];

int solve(string &s, int index) {

	if(s.size()==0) {
		int ans = p2[num-index];
		return ans;
	}

	if(index==num) {
		return 0;
	}

	if(s.size()==1) {
		int ans = dp[num][s[0]-'a'];
		ans -= dp[index][s[0]-'a'];

		ans *= power(2, num);

		ans %= MOD;
		ans += MOD;
		ans %= MOD;

		return ans;
	}

	string str1 = "";
	string str2 = "";

	for(int i=0;i<s.size();i++) {
		if(i%2==0) str1 += s[i];
		else str2 += s[i];
	}

	int f1 = 1;
	int f2 = 1;

	for(int i=0;i<s.size();i++) {
		if(i%2==0) {
			if(s[i]!=t[index]) f1 = 0;
		}
		else {
			if(s[i]!=t[index]) f2 = 0;
		}
	}

	int ans = 0;

	if(f2) ans += solve(str1, index+1);
	if(f1) ans += solve(str2, index+1);

	ans %= MOD;

	// cout<<"#"<<s<<" "<<index<<" -- "<<ans<<endl;
	return ans;
}

signed main() {
	
	fast;

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

	cin>>s>>t;

	char* s1 = new char[s.size()+1];
	strcpy(s1, s.c_str());

	for(int i=1;i<=n;i++) {
		for(int j=0;j<26;j++) {
			dp[i][j] = dp[i-1][j];
		}
		dp[i][t[i-1]-'a'] = (dp[i][t[i-1]-'a']+power(2, (MOD-1)-(i)))%MOD;
	}

	p2[0] = 1;
	for(int i=1;i<=1000000;i++) p2[i] = (p2[i-1]*2)%MOD;

	while(q--) {

		int len = s.size();

		string str;

		cin>>num;
		cin>>str;

		vector<int> match(len+1,0);

		int ans = 0;

		char* strC = new char[str.size()+1];

		strcpy(strC, str.c_str());
		KMPSearch(s1, strC, len+1, match);

		unordered_map<string,int> cnt;

		for(int i=0;i<=len;i++) {
			// cout<<"$"<<i<<endl;
			int n = str.size();
			bool f = 1;
			string str1 = "";
			for(int j=0;j<min(i,n);j++) {
				if(str[j]!=s[len-(i-j)]) {
					// cout<<"##"<<j<<" "<<len<<"-("<<i<<"-"<<j<<")"<<str[j]<<" "<<s[len-(i-j)]<<endl;
					f = 0;
				}
			}

			if(!f) continue;

			int cur = 0;
			
			int mn = i;

			if(!f) continue;

			int j = i+(n/(len + 1) + 1)*(len+1);
			while(j-(len+1)>=n) j -= len + 1;

			if(j-(len+1)<n && j-(len+1)+1>=0) {
				int cur = 0;
				// cout<<""
				for(int k=j-(len+1)+1;k<n;k++) {
					if(str[k]!=s[cur]) {
						// cout<<"$"<<i<<j-(len+1)+1<<endl;
						f=0;break;
					}
					cur++;
				}
			}

			while(j+(len+1)>n) j -= (len+1);

			int cc = (j-i)/(len+1) + 1;
			if(i==len) cc++;
			cc = max(0LL, cc);

			// cout<<"#"<<i<<" -- "<<match[i]<<" "<<cc<<endl;

			if(match[i]!=cc) f = 0;

			if(f) {
				for(int j=i;j<n;j+=(len+1)) str1 += str[j];
				cnt[str1]++;
			// cout<<"$"<<i<<" -- "<<str1<<endl;
			}
		}

		for(auto &x: cnt) {
			string s = string(x.f);
			ans += x.s*solve(s, 0)%MOD;
			ans %= MOD;
		}

		cout<<ans<<endl;
	}
}
```