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
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\)
All good strings are $$ abcc,abcb,abca,abbd,abad,aabd $$.