CF613E Puzzle Lover

Oleg Petrov 喜欢填字游戏，每周四他都会购买他最喜欢的含有填字游戏和其他文字谜题的杂志。在最新一期的杂志中，Oleg 发现了一个有趣的谜题，杂志承诺解出这个谜题将获得丰厚的奖品。我们在下面给出这个问题的正式描述。 这个谜题的棋盘包括两行，每行有 $n$ 个格子。每个格子里正好包含一个小写英文字母。同时，给定一个长度为 $k$ 的单词 $w$，单词中每个字符都是小写英文字母。一个谜题的解是一个格子序列 $c_{1}, \ldots, c_{k}$，满足： - 对所有 $i = 1, 2, \ldots, k$，格子 $c_i$ 中的字母等于 $w_i$； - 序列中的所有格子互不相同； - 对全部 $i = 1, 2, \ldots, k-1$，格子 $c_i$ 和 $c_{i+1}$ 有公共边。 Oleg Petrov 很快就找到了这个谜题的一个解。现在他想知道，这个谜题一共有多少个不同的解。由于 Oleg Petrov 不喜欢太大的数字，请你将最终答案对 $10^9+7$ 取模后输出。 如果存在某个位置 $j$，使得 $c_j \neq c'_j$，那么两个解 $c_{i}$ 和 $c'_{i}$ 被认为是不同的。

前两行给出谜题棋盘的状态。每行包含正好 $n$ 个小写英文字母。 接下来一行为空行。 下一行包含一个非空单词 $w$，长度为 $k$，由小写英文字母组成。 每行的长度不超过 $2000$。

输出一个整数，表示不同谜题解的个数，对 $10^9+7$ 取模。

由 ChatGPT 5 翻译