给定一个正整数 $N$，阶为 $N$ 的排列是一个从 $\{1, \dots, N\}$ 到其自身的双射（一一对应）函数。如果 $p$ 是这样一个函数，我们用其值的列表来表示该函数：

$[ p(1) \ p(2) \ \dots \ p(N) ]$

例如，$[5 \ 6 \ 2 \ 4 \ 7 \ 1 \ 3]$ 表示从 $\{1 \dots 7\}$ 到其自身的函数，其中 $1$ 映射到 $5$，$2$ 映射到 $6$，以此类推，直到 $7$ 映射到 $3$。

对于任何排列 $p$，如果存在整数 $k$ 使得 $p(k) > p(k+1)$，则称 $k$ 为 $p$ 的一个下降（descent）。例如，排列 $[5 \ 6 \ 2 \ 4 \ 7 \ 1 \ 3]$ 在 $2$（因为 $6 > 2$）和 $5$（因为 $7 > 1$）处有下降。

对于排列 $p$，记 $des(p)$ 为 $p$ 中下降的个数。例如，$des([5 \ 6 \ 2 \ 4 \ 7 \ 1 \ 3]) = 2$。恒等排列是唯一满足 $des(p) = 0$ 的排列。满足 $p(k) = N+1-k$ 的反转排列是唯一满足 $des(p) = N-1$ 的排列。

给定阶 $N$ 和值 $v$，排列下降计数（PDC）是指阶为 $N$ 且 $des(p) = v$ 的排列个数。例如：

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

编写一个程序来计算给定 $N$ 和 $v$ 的 $PDC$。为了避免处理非常大的数字，你的答案（以及中间计算过程）将对 $1001113$ 取模。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$)，表示随后数据组的数量。每组数据应被独立且相同地处理。

每组数据由单行输入组成。它包含数据组编号 $K$，随后是整数阶 $N$ ($2 \le N \le 100$)，以及整数值 $v$ ($0 \le v \le N-1$)。

输出格式

对于每组数据，输出一行。输出行包含数据组编号 $K$，后跟一个空格，再后跟 $N$ 和 $v$ 的 $PDC$ 对 $1001113$ 取模后的十进制整数结果。

样例

样例输入 1

4
1 3 1
2 5 2
3 8 3
4 99 50

样例输出 1

1 4
2 66
3 15619
4 325091