CF1466G.Song of the Sirens

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 \leq i \leq n$) be the $i$-th song and $t$ be a string of length $n$, then for every $i \lt 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$.

凡无知者趋近她们，听闻塞壬之歌声，便永无归途。

荷马，《奥德赛》

在伊阿宋与阿尔戈英雄们的时代，世人皆知塞壬以歌声引诱水手走向毁灭。然而，仅少数人知晓：每当塞壬呼唤水手之名，其意志便随之衰弱，从而更易受其蛊惑。

本题中，塞壬的歌声与水手的名字均以小写英文字母组成的字符串表示。水手之名作为歌声中连续子串出现的次数越多，其处境便越危险。

伊阿宋发现，塞壬可吟唱 $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$ 首歌曲由第 $i$ 首歌曲、字符串 $t$ 的第 $i$ 个字符（从 $0$ 开始索引）以及第 $i$ 首歌曲拼接而成。

幸运的是，伊阿宋已知 $s_0$ 与 $t$。他想知道某位水手的名字在特定歌曲中被提及多少次。请回答 $q$ 个查询：给定水手的名字 $w$ 与歌曲编号 $i$，输出 $w$ 在 $s_i$ 中作为子串出现的次数；由于该数值可能极大，请输出其对 $10^9+7$ 取模的结果。

In the first line of input there are two integers $n$, $q$ ( $ 1 \leq n, q \leq 10^5$) meaning that there are $n+1$ songs and $q$ queries. In the next two lines strings $s_0$ and $t$ follow ($1 \leq |s_0| \leq 100, |t| = n$).

Next $q$ lines describe the queries; each one contains an integer $k$ ($ 0 \leq k \leq 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$.

输入的第一行包含两个整数 $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$。

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$.

输出 $q$ 行，其中第 $i$ 行应包含子串 $w$ 在 $s_k$ 中出现次数对 $10^9+7$ 取模的结果。

In the first example songs of the sirens are as follows:

• Song $0$: aa
• Song $1$: aabaa
• Song $2$: aabaacaabaa
• Song $3$: aabaacaabaadaabaacaabaa

在第一个例子中，塞壬的歌曲如下：

• 歌曲 $0$: aa
• 歌曲 $1$: aabaa
• 歌曲 $2$: aabaacaabaa
• 歌曲 $3$: aabaacaabaadaabaacaabaa