D. String From Another World
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Scientists from the NewEra got a string $$$s$$$ of length $$$n$$$ which contains lowercase English letters from far away space.

They have a machine which is capable of doing exactly one of the following operations in one second with an empty string $$$t$$$:

  1. Choose any lowercase English character and append it to the end of $$$t$$$.
  2. If $$$t$$$ is empty, do nothing; otherwise, remove the last character from $$$t$$$.

Scientists got information that within $$$m$$$ seconds the machine will die, so they decided to generate a copy of $$$s$$$ in $$$m$$$ seconds, i.e., they want to make $$$t = s$$$ by using the machine for exactly $$$m$$$ seconds.

Now the scientists are wondering in how many different ways they can make $$$t = s$$$ modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$tc$$$ ($$$1 \le tc \le 1000$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ ($$$1 \le n,m \le 8000$$$), the length of the string and the deadline of the machine.

The second line of each testcase contains a string $$$s$$$ of length $$$n$$$ which contains lowercase English letters.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases doesn't exceed $$$8000$$$.

Output

For each test case, print a single integer — the number of different ways to make $$$t = s$$$ modulo $$$10^9+7$$$.

Example
Input
5
3 4
abc
1 3
d
5 3
asdfg
7 10
wuhudsm
9 11
yugandhar
Output
1
53
0
235
261