B. Shoot Parachute Brainroot
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

While 3atori and Habbab battle it out in CS2 and PUBG, this problem is all yours.

You are given a string $$$s$$$ of length $$$n$$$ and an even integer $$$k$$$.

Consider the $$$n$$$ suffixes of $$$s$$$, one suffix for each starting position. Choose exactly $$$k$$$ of these suffixes. The score of the chosen set is the number of distinct non-empty strings $$$p$$$ such that $$$p$$$ is a prefix of at least $$$\frac{k}{2}$$$ chosen suffixes.

Compute the sum of scores over all ways to choose exactly $$$k$$$ suffixes. Since the answer can be large, print it modulo $$$10^9 + 7$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of a test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 10^6$$$, $$$k$$$ is even).

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print one integer — the sum of scores over all choices of exactly $$$k$$$ suffixes, modulo $$$10^9 + 7$$$.

Example
Input
3
2 2
ab
3 2
aba
6 4
abcaec
Output
3
11
12
Note

In the first test case, the two suffixes are $$$\texttt{ab}$$$ and $$$\texttt{b}$$$. Since $$$k=2$$$, both suffixes must be chosen, and a string is counted if it is a prefix of at least one chosen suffix.

The counted strings are $$$\texttt{a}$$$, $$$\texttt{ab}$$$, and $$$\texttt{b}$$$, so the answer is $$$3$$$.

In the second test case, the suffixes are $$$\texttt{aba}$$$, $$$\texttt{ba}$$$, and $$$\texttt{a}$$$. We choose two suffixes, and again a string is counted if it is a prefix of at least one chosen suffix.

If we choose $$$\texttt{aba}$$$ and $$$\texttt{ba}$$$, the score is $$$5$$$. If we choose $$$\texttt{aba}$$$ and $$$\texttt{a}$$$, the score is $$$3$$$. If we choose $$$\texttt{ba}$$$ and $$$\texttt{a}$$$, the score is $$$3$$$. Therefore the total answer is $$$5+3+3=11$$$.