problem provider: Jackson_Miller

题目描述

给定 $2$ 个长度为 $N$ 的字符串 $A,B$，由大写字母组成的 $i$ 行 $j$ 列的串，和长度为 $M$ 的字符串 $S$。

只要将由大写字母选出构成的字符串与 $S$ 相同，那就是个合法的位置。

输出合法位置的个数 $\bmod\ 1007$ 的结果。

我们认为两个字符串不相同，当且仅当存在一个位置 $i$ 使得 $S_i \neq S'_i$ 。

约束条件

• $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)$。