A subsequence of a string is a new string that is formed by deleting some (or none) of the characters from the original string, without changing the order of the remaining characters.

A special subsequence of a string is subsequence that has the following properties:

1. It has length exactly K.
2. It contains all Unique characters.
3. The sum of frequencies of all the characters in the subsequence is the maximum possible sum among all special subsequence of length k.

Given a String S and an integer K, find the number of distinct special subsequences of the string. Since the number of special subsequences can be large, print the answer modulo 1e9 + 7.

Input Format:

1. First line contains an integer T, denoting number of test cases,
2. for each test case :
   i. First line contains an integer N.
   ii. Second Line contains an integer K.
   iii. Next Line contains an String S.

Output Format:
For each test case, print the required answer in a new line.

Constraints:
1 <= T <= 10
1 <= N <= 1e5
1 <= K <= N
S contains only latin lowercase letters.

Example 1:
Input:
1
5
4
cppbg

Output: 2
Expalnation : cpbg (includes p at index 1), cpbg(includes p at index 2).

Example 2:
Input:
1
12
8
fpbavjsmppdt

Output: 108

Example 3:
Input:
1
16
7
ppzfsncqyzmuwrcv

Output: 1680