#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

In order to communicate some emergency information, Peanut has sent Gug a string *S* consisting of *N* uppercase characters.

Within this string, Peanut has added a secret verification scheme. He has told Gug that a shorter string, *T*, of *M* uppercase characters, will appear many times as a **subsequence** of *S*. *T* is said to be a subsequence of *S* if it is possible to remove some letters in *S* such that the remaining letters form *T*.

Help Gug figure out how many times *T* appears as a subsequence in *S*, modulo 10^{9} + 7. Two ways are considered different if the positions of the letters removed are different.

## Limits

For all subtasks: 1 ≤ N ≤ 3 000 000, 1 ≤ M ≤ 10.

Subtask 1 (13%): S and T will only consist of 'A's.

Subtask 2 (7%): S will consist of a non-negative number of 'A's, followed by a non-negative number of 'B's. (e.g. AABBBB), T = "AB".

Subtask 3 (6%): M = 1.

Subtask 4 (10%): M ≤ 2.

Subtask 5 (12%): M ≤ 3.

Subtask 6 (11%): N ≤ 20.

Subtask 7 (16%): N ≤ 1 000.

Subtask 8 (8%): N ≤ 100 000.

Subtask 9 (17%): No additional constraints.

Subtask 10 (0%): Sample Testcases.

## Input

The first line of input will contain two integers, *N* and *M*.

The second line of input will contain one string, *S*.

The third line of input will contain one string, *T*.

## Output

The output should contain one line with one integer, the number of times *T* appears as a subsequence of *S*, modulo 10^{9} + 7.

## Sample Input 1

6 3 BANANA ANA

## Sample Output 1

4

## Explanation for Sample 1

B**ANA**NA, B**A**NA**NA**, B**AN**AN**A**, BAN**ANA**.

## Sample Input 2

6 2 MEOWWW OW

## Sample Output 2

3

## Sample Input 3

7 2 AAAAABB AB

## Sample Output 3

10

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 13 | 20 | 1s | 256MB | Minimum |

2 | 7 | 21 | 1s | 256MB | Minimum |

3 | 6 | 20 | 1s | 256MB | Minimum |

4 | 10 | 62 | 1s | 256MB | Minimum |

5 | 12 | 83 | 1s | 256MB | Minimum |

6 | 11 | 23 | 1s | 256MB | Minimum |

7 | 16 | 43 | 1s | 256MB | Minimum |

8 | 8 | 63 | 1s | 256MB | Minimum |

9 | 17 | 183 | 1s | 256MB | Minimum |

10 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o hidden -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512