在伊阿宋和阿尔戈英雄的时代,众所周知,塞壬会利用歌声来引诱水手走向灭亡。然而只有少数人知道,每当海妖叫出水手的名字时,他的意志就会减弱,使他变得更加脆弱。
出于此问题的目的,海妖之歌和水手的名字都将表示为小写英文字母的字符串。水手的名字作为歌曲的连续子串出现的次数越多,他面临的危险就越大。
Jason 发现塞壬可以唱 $$$n+1$$$ 歌曲中的一首,其结构如下:设 $$$s_i$$$ ($$$0 \leq i \leq n$$$) 为第 $$$i$$$ 歌曲,$$$t$$$ 为长度为 $$$n$$$ 的字符串,则对于每个 $$$i < n$$$: $$$s_{i+1} = s_i t_i s_i$$$。换句话说,$$$i+1$$$-st 歌曲是 $$$i$$$-th 歌曲、$$$t$$$ 的 $$$i$$$-th 字母($$$0$$$-索引)和 $$$i$$$-th 歌曲的串联。
幸运的是,他也认识$$$s_0$$$和$$$t$$$。杰森想知道某首歌曲中提到了多少次水手的名字。回答$$$q$$$查询:给定水手的名字($$$w$$$)和歌曲索引($$$i$$$),输出$$$w$$$在$$$s_i$$$中出现的次数作为子字符串。由于这个数字可能非常大,因此输出其对 $$$10^9+7$$$ 取模后的余数。
输入
输入的第一行有两个整数 $$$n$$$、$$$q$$$ ( $$$ 1 \leq n, q \leq 10^5$$$) 意味着有 $$$n+1$$$ 歌曲和 $$$q$$$ 查询。接下来的两行是字符串 $$$s_0$$$ 和 $$$t$$$ ($$$1 \leq |s_0| \leq 100, |t| = n$$$)。
接下来的 $$$q$$$ 行描述查询;每个都包含一个整数 $$$k$$$ ($$$ 0 \leq k \leq n$$$),即海妖所唱歌曲的索引,以及一个非空字符串 $$$w$$$,它是一个水手的名字。该问题中的所有字符串仅由小写英文字母组成,并且水手名字的长度总和不超过$$$10^6$$$。
输出
输出 $$$q$$$ 行,其中 $$$i$$$ 应包含 $$$s_k$$$ 中 $$$w$$$ 出现次数的模 $$$10^9+7$$$ 的余数。
示例
输入 #1
3 3 aa bcd 2 aba 3 ca 3 aa
输出 #1
2 2 8
输入 #2
4 5 aba bbac 1 a 3 baca 3 ab 2 bab 4 aba
输出 #2
4 0 14 6 28
注意
在第一个示例中,海妖的歌曲如下:
- 歌曲 $$$0$$$: aa
- 歌曲 $$$1$$$: aabaa
- 歌曲 $$$2$$$: aabaacaabaa
- 歌曲 $$$3$$$: aabaacaabaadaabaacaabaa