Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

Given a letter matrix $S$ with $2$ rows and $n$ columns.

Count the number of positions that meet the following condition: there is a path of length $m$ that starts from that position (each time you can go up/down/left/right by one position; passing the same position twice is allowed), where the letters on the $m$ positions passed through are $T_1,T_2,\ldots,T_m$, respectively.

Take the answer modulo $1007$.

Input Format

The first line contains two positive integers $n, m\ (1 \le n, m \le 2000)$.

Each of the next two lines contains $n$ characters, representing $S$.

The last line contains $m$ characters, representing $T$.

Output Format

The count of valid positions modulo $1007$.

The solution is guaranteed to exist.

Samples

4 4
LOVE
EVOL
LOVE

4

1 3
Y
Y
YYY

2

5 5
MLMRC
LLLCP
LMRCP

4

Sample 1 Explanation

• Possibility 1: $(1,1) \to (1,2) \to (1,3) \to (1,4)$;
• Possibility 2: $(1,1) \to (1,2) \to (2,2) \to (2,1)$;
• Possibility 3: $(2,4) \to (2,3) \to (2,2) \to (2,1)$;
• Possibility 4: $(2,4) \to (2,3) \to (1,3) \to (1,4)$.

Sample 2 Explanation

• Possibility 1: $(1,1) \to (1,2) \to (1,1)$;
• Possibility 2: $(1,2) \to (1,1) \to (1,2)$.

Sample 3 Explanation

• Possibility 1: $(3,2)\to(3,1)\to(4,1)\to(4,2)\to(5,2)$;
• Possibility 2: $(2,1)\to(3,1)\to(4,1)\to(4,2)\to(5,2)$;
• Possibility 3: $(3,2)\to(3,1)\to(4,1)\to(5,1)\to(5,2)$;
• Possibility 4: $(2,1)\to(3,1)\to(4,1)\to(5,1)\to(5,2)$.