版权声明

本题版权归 Long Long OJ 所有。

题目描述

给定一个 $2$ 行 $n$ 列的字母矩阵 $S$。

请问：存在多少条长度为 $m$ 的路径（每次可以向上 / 下 / 左 / 右走一格，允许重复经过同一个格子），使得所经过的 $m$ 个格子上的字母依次为 $T_1,T_2,\ldots,T_m$？

答案对 $1007$ 取模。

输入格式

第一行两个正整数 $n,m$。

下面两行，每行 $n$ 个大写字母，表示矩阵 $S$。

最后一行 $m$ 个大写字母，表示字符串 $T$。

输出格式

合法路径的个数 $\bmod\ 1007$。

样例

4 4
LOVE
EVOL
LOVE

4

1 3
Y
Y
YYY

2

5 5
MLMRC
LLLCP
LMRCP

4

提示

样例 $1$ 解释：

• 可能性 1：$(1,1)\to(1,2)\to(1,3)\to(1,4)$；
• 可能性 2：$(1,1)\to(1,2)\to(2,2)\to(2,1)$；
• 可能性 3：$(2,4)\to(2,3)\to(2,2)\to(2,1)$；
• 可能性 4：$(2,4)\to(2,3)\to(1,3)\to(1,4)$。

样例 $2$ 解释：

• 可能性 1：$(1,1)\to(1,2)\to(1,1)$；
• 可能性 2：$(1,2)\to(1,1)\to(1,2)$。

样例 $3$ 解释：

• 可能性 1：$(3,2)\to(3,1)\to(4,1)\to(4,2)\to(5,2)$；
• 可能性 2：$(2,1)\to(3,1)\to(4,1)\to(4,2)\to(5,2)$；
• 可能性 3：$(3,2)\to(3,1)\to(4,1)\to(5,1)\to(5,2)$；
• 可能性 4：$(2,1)\to(3,1)\to(4,1)\to(5,1)\to(5,2)$。

对于 $100\%$ 的数据，$1\le n \le2000$，$1\le m \le2000$，保证有解。