22747_MaximumintheCycleof1

If P is a pemutatlon of the integers 1, …, n , the maximum in the cycle of 1 is the maximum of the values P(1) , P(P(1)) , P(P(P(1))) , etc. For example, if P is the permutation :

| 1 2 3 4 5 6 7 8 |

| 3 2 5 4 1 7 8 6 |

we have :

P(1) = 3

P(P(1)) = P(3) = 5

and

P(P(P(1))) = P(5) = 1

so the rnaximum in the Cycle of 1 is 5.

For this problem , you will write a program which takes as input integers n, ( n > 0 ) and k ( 1 ≤ k ≤ n ), and returns the number of permutations of the integers 1, …, n , for which the maximum in the cycle of 1 is k .

The first line of input contains a single integer P, ( 1 ≤ P ≤ 1000 ), which is the number of data sets that follow. Each data set is a single line that contains the three space separated decimal integer values. The first value is the data set number, N. The second value is the size of the permutatlon , n where ( 1 ≤ n ≤ 20 ), and the third value is the desired maximum in the cycle of 1, k where ( 1 ≤ k ≤ n ）.

For each data set there is one line of output. It contains the data set number ( N ) followed by a double precision floating point whole value which is the number of permutations of the integers 1, …, n , for which the maximum in the Cycle of 1 is k .

4
1 4 1
2 7 3
3 10 5
4 20 7

1 6
2 168
3 86400
4 1158524765798400