eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Maximum in the Cycle of 1

Maximum in the Cycle of 1

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

If P is a permutation 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) = 3P(P(1)) = P(3) = 5

and

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

so the maximum 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 (1kn), 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 (1P1000), 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 permutation, n where (1n20), and the third value is the desired maximum in the cycle of 1, k where (1kn).

Выходные данные

For each data set there is one line of output. It contains the data set number N followed by a single space, 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.

Пример

Входные данные #1
4
1 4 1
2 7 3
3 10 5
4 20 7
Выходные данные #1
1 6
2 168
3 86400
4 11585247657984000
Источник 2011 Greater New York Regional