순열의 하강 개수

양의 정수 $N$에 대해 차수 $N$의 순열은 1부터 $N$까지의 정수 집합에서 자기 자신으로 가는 일대일 대응이다. 이런 함수 $p$는 함숫값을 차례로 나열해 [p(1) p(2) ... p(N)]로 쓴다.

예를 들어 [5 6 2 4 7 1 3]은 {1, ..., 7}에서 자기 자신으로 가는 함수로, 1을 5로, 2를 6으로, 같은 식으로 7을 3으로 보낸다.

순열 $p$의 하강은 $p(k) > p(k+1)$을 만족하는 정수 $k$다. 순열 [5 6 2 4 7 1 3]은 2에서 (6 > 2), 5에서 (7 > 1) 하강한다.

$\mathrm{des}(p)$를 $p$의 하강 개수라고 하면 [5 6 2 4 7 1 3]의 $\mathrm{des}$ 값은 2다. $\mathrm{des}(p) = 0$인 순열은 항등 순열 하나뿐이고, $\mathrm{des}(p) = N-1$인 순열은 $p(k) = N+1-k$로 정의되는 역순 순열 하나뿐이다.

차수 $N$과 값 $v$에 대한 순열 하강 개수 $\mathrm{PDC}(N, v)$는 $\mathrm{des}(p) = v$인 차수 $N$의 순열 $p$의 개수다. 차수가 3이면 다음과 같다.

• $\mathrm{PDC}(3, 0) = 1$, 해당 순열은 [1 2 3]
• $\mathrm{PDC}(3, 1) = 4$, 해당 순열은 [1 3 2], [2 1 3], [2 3 1], [3 1 2]
• $\mathrm{PDC}(3, 2) = 1$, 해당 순열은 [3 2 1]

주어진 $N$과 $v$에 대해 $\mathrm{PDC}(N, v)$를 구한다. 개수가 아주 커지므로 답과 중간 계산 모두 1001113으로 나눈 나머지로 다룬다.

첫 줄에 데이터 세트의 개수 $P$ ($1 \le P \le 1000$)가 주어진다. 모든 데이터 세트는 같은 방식으로, 서로 독립적으로 처리한다.

각 데이터 세트는 한 줄이다. 데이터 세트 번호 $K$, 차수 $N$ ($2 \le N \le 100$), 값 $v$ ($0 \le v \le N-1$)가 순서대로 주어진다.

데이터 세트마다 한 줄씩 출력한다. 한 줄에는 데이터 세트 번호 $K$, 공백 하나, $\mathrm{PDC}(N, v)$를 1001113으로 나눈 나머지를 십진 정수로 적는다.