Given a string $S$ of length $N$ consisting of only lower case alphabets. Print the total count of good strings. A string is called good if:-

- its length is $N$ and consists of only lower case alphabets.
- it mismatches with $S$ at exactly $K$ different indexes.
- it is lexicographically smaller than $S$.

Since the answer could be large print it with modulo $10^9 + 7$.

 Input format

• The first line contains $T$ denoting the number of test cases.
• The first line of each test case contains integers $N$ and $K$, denoting the size of the length of the $S$ and mismatch count.
• The next line contains $S$.

Output format

Print the number of total possible good strings. Since the answer could be large print it with modulo $10^9 + 7$.

Constraints

$1 \leq T \leq 5000$
$1 \leq N \leq 10^5$
$1 \leq K \leq 20$
The sum of $N$ over all test cases does not exceed $2 \cdot 10^5$