CF613E.Puzzle Lover

Oleg Petrov loves crossword puzzles and every Thursday he buys his favorite magazine with crosswords and other word puzzles. In the last magazine Oleg found a curious puzzle, and the magazine promised a valuable prize for it's solution. We give a formal description of the problem below.

The puzzle field consists of two rows, each row contains n cells. Each cell contains exactly one small English letter. You also are given a word w, which consists of k small English letters. A solution of the puzzle is a sequence of field cells _c_1, ..., c__k, such that:

• For all i from 1 to k the letter written in the cell c__i matches the letter w__i;
• All the cells in the sequence are pairwise distinct;
• For all i from 1 to k - 1 cells c__i and c__i + 1 have a common side.

Oleg Petrov quickly found a solution for the puzzle. Now he wonders, how many distinct solutions are there for this puzzle. Oleg Petrov doesn't like too large numbers, so calculate the answer modulo 109 + 7.

Two solutions c__i and c'i are considered distinct if the sequences of cells do not match in at least one position, that is there is such j in range from 1 to k, such that c__j ≠ c'j.

奥列格·彼得罗夫热爱填字游戏，每周四他都会购买自己最喜爱的填字杂志及其他文字类谜题刊物。在最近一期杂志中，奥列格发现了一道有趣的谜题，杂志承诺将为该谜题的正确解答提供一份丰厚奖品。下面我们给出该问题的形式化描述。

谜题的棋盘由两行组成，每行包含 $n$ 个格子。每个格子中恰好填有一个小写英文字母。同时，你还会得到一个由 $k$ 个小写英文字母组成的单词 $w$。该谜题的一个解是一串棋盘上的格子序列 $c_1, \dots, c_k$，满足以下条件：

• 对所有 $i$（从 $1$ 到 $k$），格子 $c_i$ 中所填字母与单词 $w$ 的第 $i$ 个字母 $w_i$ 相同；
• 序列中所有格子互不相同；
• 对所有 $i$（从 $1$ 到 $k-1$），格子 $c_i$ 与 $c_{i+1}$ 必须有公共边（即上下左右相邻）。

奥列格·彼得罗夫很快便找到了该谜题的一个解。现在他想知道：这个谜题一共有多少个不同的解？由于奥列格不喜欢过大的数字，请将答案对 $10^9 + 7$ 取模后输出。

若两个解 $c_i$ 和 $c'_i$ 在至少一个位置 $j$（其中 $j$ 取值范围为 $1$ 到 $k$）上满足 $c_j \ne c'_j$，则认为这两个解是不同的。

The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly n small English letters.

The next line is left empty.

The next line is non-empty and contains word w, consisting of small English letters.

The length of each line doesn't exceed 2 000.

前两行包含谜题中方格的状态。每行均为非空行，且恰好包含 n 个小写英文字母。

接下来一行为空行。

再下一行为非空行，包含单词 w，由小写英文字母组成。

每行的长度均不超过 2 000。

Print a single integer — the number of distinct solutions for the puzzle modulo 109 + 7.

输出一个整数——该谜题的不同解的数目对 $10^9 + 7$ 取模的结果。