← 返回题目列表

Codeforces · 613/E

E. 拼图爱好者

中文机器翻译题面 查看原题

Oleg Petrov 喜欢填字游戏,每个星期四他都会购买他最喜欢的杂志,里面有填字游戏和其他填字游戏。在上一本杂志中,奥列格发现了一个奇怪的谜题,该杂志承诺为解决该谜题提供宝贵的奖励。我们在下面给出问题的正式描述。

拼图字段由两行组成,每行包含 n 个单元格。每个单元格恰好包含一个小英文字母。还给出了一个单词 w,它由 k 个小英文字母组成。该难题的一个解决方案是一系列场单元 c1, ..., ck,使得:

- 对于从 1 到 k 的所有 i,单元格 ci 中写入的字母与字母 wi 匹配;
- 序列中的所有单元格都是成对不同的;
- 对于所有 i 从 1 到 k - 1 个单元格 ci 和 ci + 1 具有公共边。

奥列格彼得罗夫很快找到了这个难题的解决方案。现在他想知道这个难题有多少种不同的解决方案。 Oleg Petrov 不喜欢太大的数字,因此计算答案以 109 + 7 为模。

如果单元序列在至少一个位置不匹配,即存在从 1 到 k 的范围内的 j,使得 cj ≠ c'j,则两个解 ci 和 c'i 被认为是不同的。

输入

前两行包含拼图字段的状态。这些非空行中的每一行都恰好包含 n 个小英文字母。

下一行留空。

下一行非空,包含单词 w,由小英文字母组成。

每行长度不超过 2 000。

输出

打印一个整数 — 谜题的不同解的数量以 109 + 7 为模。

示例

输入 #1

code
edoc
code

输出 #1

4

输入 #2

aaa
aaa
aa

输出 #2

14