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