Pascal Matrix Power

The Pascal matrix is infinite in size, and its rows and columns are numbered from 0. Each entry is defined as follows.

Pascal[row, column] = Comb(row, column)   (0 ≤ column ≤ row)

Every position outside that range holds 0. Comb(n, k) is the number of ways to choose k items out of n distinct items.

Let PascalP be the product of $P$ copies of the Pascal matrix.

PascalP = Pascal × Pascal × ... × Pascal

Write a program that computes a single entry of PascalP.

The first line contains the number of test cases $K$ ($1 \leq K \leq 1000$).

Each of the next $K$ lines holds one test case as four integers. The first integer is the test case number, the second integer is $P$ ($1 \leq P \leq 100000$), and the third and fourth integers are $R$ and $C$ ($0 \leq C \leq R \leq 100000$).

For each test case, print the test case number and the entry of PascalP at row $R$, column $C$ on one line, separated by a single space.

Only inputs whose answer fits in a 64-bit integer are given.