Source

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

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$.

Constraints

• $1 \leq N \leq 2000$ and $1 \leq M \leq 2000$.
• The solution is guaranteed to exist.

Input

$N\ M$ $A_1A_2\cdots A_N$ $B_1B_2\cdots B_N$ $S_1S_2\cdots S_M$

• The first line contains two positive integers $N$ and $M$.
• The next two lines contain strings $A$ and $B$.
• The last line contains $M$ characters representing $S$.

Output

The count of valid positions modulo $1007$.

Sample Input 1

4 4
LOVE
EVOL
LOVE

Sample Output 1

4

• 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 Input 2

1 3
Y
Y
YYY

Sample Output 2

2

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