#11481Arrange the Numbers

Consider this sequence {1, 2, 3, . . . , N }, as a initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be N ! different arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M (M ≤ N ) positions, exactly K (K ≤ M ) numbers are in its initial position.

Example:

For, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1-st position and 3 in 3-rd position. So exactly 2 of its first 3 are in there initial position.

But you should not count this {1, 2, 3, 4, 5}.

Input

The first line of input is an integer T (T ≤ 1000) that indicates the number of test cases. Next T line contains 3 integers each, N (1 ≤ N ≤ 1000), M , and K.

Output

For each case, output the case number, followed by the answer modulo 1000000007. Look at the sample for clarification.

1
5 3 2

Case 1: 12