版权声明

本题版权归 Long Long OJ 所有。

题目描述

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

请求出满足以下条件的位置个数：存在一条长度为 $m$ 且从该位置出发的路径（每次可以向上 / 下 / 左 / 右走一格，允许重复经过同一个格子），使得所经过的 $m$ 个格子上的字母依次为 $T_1,T_2,\ldots,T_m$。

答案对 $1007$ 取模。

约束条件

• $1\le n \le2000$ 且 $1\le m \le2000$。
• 保证答案有解。

输入格式

$N\ M$

$A_1A_2\cdots A_N$

$B_1B_2\cdots B_N$

$S_1S_2\cdots S_M$

• 第一行两个正整数 $N,M$。
• 接下来 $2$ 行为字符串 $A,B$。
• 最后一行 $M$ 个字符，表示 $S$。

输出格式

合法位置的个数 $\bmod\ 1007$。

样例输入 1

4 4
LOVE
EVOL
LOVE

样例输出 1

4

• 可能性 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 3 
Y
Y
YYY

样例输出 2

2

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