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\)