H. Heritage of Acatlán
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Library of Acatlán, an ancient spell is written as a long string $$$S$$$ of length $$$N$$$. The spell also contains a secret incantation $$$T$$$, a string of length $$$M$$$.

The power of the spell is measured by the number of subsequences of $$$S$$$ that are equal to $$$T$$$.

The oracle of Acatlán allows you to perform at most one modification on $$$S$$$: you may change a single character in $$$S$$$ to any other lowercase English letter.

Your task is to count the power of all the possible spells with at most one modification.

Definition: A string $$$U$$$ is called a subsequence of a string $$$V$$$ if $$$U$$$ can be obtained from $$$V$$$ by deleting zero or more characters without changing the relative order of the remaining characters.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 60$$$) — the lengths of the strings $$$S$$$ and $$$T$$$.

The second line contains the string $$$S$$$.

The third line contains the string $$$T$$$.

Both strings consist of lowercase English letters.

Output

Print a single integer, the accumulated power of all possible spells with at most one modification number of subsequences of $$$S$$$ that contain $$$T$$$ after at most one modification, because this number can be very big, print it modulo $$$10^9 + 7$$$

Examples
Input
3 2
cac
ac
Output
27
Input
3 3
abc
abc
Output
1
Note

For the first sample case, if we modify any of the last two characters, we won't have any subsequence equal to $$$T$$$. In addition, the only modification of the first character that makes $$$S$$$ to have two subsequences equal to $$$T$$$ is with the letter 'a'. The other modifications or no modification just keep the number of subsequences in $$$1$$$, so we have $$$2 \times 1 + 1 \times 25 = 27$$$.

For the second sample case, the only scenario in which the string $$$S$$$ contains a subsequence equal to $$$T$$$ is when we don't apply modifications at all. Any modification would imply that $$$S$$$ won't contain $$$T$$$ as a subsequence. Therefore, the answer is $$$1$$$.