Permutation Descent Counts

For a positive integer $N$, a permutation of order $N$ is a one to one function from the set of integers 1 through $N$ onto itself. Such a function $p$ is written as the list of its values, [p(1) p(2) ... p(N)].

For example, [5 6 2 4 7 1 3] is the function on {1, ..., 7} that sends 1 to 5, 2 to 6, and so on through 7 to 3.

A descent of a permutation $p$ is an integer $k$ with $p(k) > p(k+1)$. The permutation [5 6 2 4 7 1 3] has a descent at 2 (6 > 2) and at 5 (7 > 1).

Let $\mathrm{des}(p)$ be the number of descents of $p$, so $\mathrm{des}$ of [5 6 2 4 7 1 3] is 2. The identity permutation is the only permutation with $\mathrm{des}(p) = 0$, and the reversing permutation given by $p(k) = N+1-k$ is the only permutation with $\mathrm{des}(p) = N-1$.

The permutation descent count $\mathrm{PDC}(N, v)$ is the number of permutations $p$ of order $N$ with $\mathrm{des}(p) = v$. For order 3:

• $\mathrm{PDC}(3, 0) = 1$, counting [1 2 3]
• $\mathrm{PDC}(3, 1) = 4$, counting [1 3 2], [2 1 3], [2 3 1], [3 1 2]
• $\mathrm{PDC}(3, 2) = 1$, counting [3 2 1]

Compute $\mathrm{PDC}(N, v)$ for the given $N$ and $v$. The counts get very large, so the answer and every intermediate value are taken modulo 1001113.

The first line contains one integer $P$ ($1 \le P \le 1000$), the number of data sets that follow. Every data set is processed in the same way and independently of the others.

Each data set is one line. It contains the data set number $K$, then the order $N$ ($2 \le N \le 100$), then the value $v$ ($0 \le v \le N-1$).

Print one line for each data set. The line holds the data set number $K$, a single space, and $\mathrm{PDC}(N, v)$ modulo 1001113 as a decimal integer.