In a planet far away from Earth, there is a deadly war going on between two countries: Bitland and
Byteland. The queen of Bitland has an army of N soldiers. She has found a strategy to attack the
weakest part of the border of Byteland, but to reach there, the soldiers of Bitland has to form a queue
and pass through a very narrow valley. Moreover, there is some defense mechanism set in the valley
by Byteland: If any soldier P with height v passes through the valley, then anybody following P with
height (strictly) greater than v will be killed by automatic firing.
The queen of Bitland is also aware of this scenario, but it is not always possible to send her soldiers
according to the non-increasing order of heights (so that no soldier dies).She understands that some
soldiers have to sacrifice their lives. To find the best possible permutation, she wants your help to
calculate the number of different permutations of the heights of her soldiers so that exactly K
soldiers die in that valley.
A permutation is X different from another permutation Y if there exists some i (1 ≤ i ≤ N) for which
the height of i-th soldier is different in these two permutations.
Input
The first line of input file contains the number of test cases, T (1 ≤ T ≤ 20). Then T cases follow:
Each case consists of two lines. The first line contains two integers: N (1 ≤ N ≤ 50000) and K
(0 ≤ K ≤ 1000). Then the second line contains N integers denoting the heights of the soldiers. There
will be at most 100 different values of their heights. There will be at most 1000 soldiers with same
height.
For 80% of the cases, N will be less than 10000.
Output
For each case, print “Case <x>: <y>” in a separate line, where x is the case number and y is the
number of permutations such that exactly K soldiers die. As the number can be very large,
print y modulo 1000000007

Example

Input:
3
3 1
1 2 3
3 1
1 2 2
3 2
1 2 3

Output:
Case 1: 3
Case 2: 1
Case 3: 2