CF1466G Song of the Sirens

无知者若靠近她们，听到塞壬的歌声，便再也无法归来。——荷马，《奥德赛》 在杰森与阿尔戈英雄的时代，人们都知道塞壬用歌声诱使水手走向毁灭。但只有极少数人知道，每当塞壬用水手的名字呼唤他时，他的意志就会减弱，变得更加脆弱。 在本题中，塞壬的歌声和水手的名字都用小写英文字母组成的字符串表示。水手的名字在歌声中作为连续子串出现的次数越多，他就越危险。 杰森发现，塞壬可以唱出 $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$ 首歌、第 $i$ 个字母（从 $0$ 开始编号）的 $t$ 以及第 $i$ 首歌依次拼接而成。 幸运的是，他还知道 $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$ 行输出 $w$ 在 $s_k$ 中出现的次数对 $10^9+7$ 取模后的结果。

在第一个样例中，塞壬的歌如下： - 歌 $0$：aa - 歌 $1$：aabaa - 歌 $2$：aabaacaabaa - 歌 $3$：aabaacaabaadaabaacaabaa 由 ChatGPT 4.1 翻译