帕斯卡矩阵（Pascal matrix）是一个（无限）矩阵，定义如下（行和列均从 0 开始）：

$\text{Pascal}[\text{row}, \text{column}] = \text{Comb}(\text{row}, \text{column})$，当 $0 \le \text{column} \le \text{row}$ 时，

其他情况为 0，其中 $\text{Comb}(n, k)$ 是从 $n$ 个元素中选取 $k$ 个元素的组合数（二项式系数）。

$$ \begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 5 & 10 & 10 & 5 & 1 & 0 & 0 & 0 & \dots \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 & \dots \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & 0 & \dots \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & \dots \\ 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & \dots \\ . & . & . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . & . & . \end{matrix} $$

对于本题，你需要编写一个程序来计算帕斯卡矩阵的幂的各项：

$\text{Pascal}^P = \text{Pascal} \times \text{Pascal} \times \dots \times \text{Pascal}$ ($P$ 个因子)

由于该矩阵是下三角矩阵，其幂也是下三角矩阵，且在计算幂矩阵左上角 $N \times N$ 区域的系数时，仅需使用原矩阵左上角 $N \times N$ 的区域。

输入格式

输入的第一行包含一个整数 $K$ ($1 \le K \le 1000$)，表示后续的数据集数量。每个数据集应独立处理。

每个数据集由一行输入组成，包含四个以空格分隔的十进制整数。第一个整数是数据集编号。第二个整数是幂次 $P$ ($1 \le P \le 100,000$)，即对帕斯卡矩阵进行幂运算的次数。第三个和第四个整数分别给出了行号 $R$ 和列号 $C$ ($0 \le C \le R \le 100,000$)，表示所求条目的位置。

输出格式

对于每个数据集，输出一行。该行包含数据集编号，后跟一个空格，再后跟帕斯卡矩阵幂运算后对应位置的数值。输入值将受到限制，以确保结果不会超过 64 位整数的范围。

样例

输入 1

3
1 1 8 3
2 9 21 13
3 200 100000 99998

输出 1

1 56
2 8759577256290
3 199998000000000

Figure 1. Pascal matrix