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 109+7.
Input format
Output format
Print the number of total possible good strings. Since the answer could be large print it with modulo 109+7.
Constraints
1≤T≤5000
1≤N≤105
1≤K≤20
The sum of N over all test cases does not exceed 2⋅105
All good strings are abcc,abcb,abca,abbd,abad,aabd.