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$ and $M$.
• The next two lines contain strings $A$ and $B$.
• The last line contains $M$ characters representing $S$.

Output Format

The count of valid positions modulo $1007$.

Samples

4 4
LOVE
EVOL
LOVE

4

1 3
Y
Y
YYY

2

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

Data Range

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