Powers of Pascal#6394
Sign in

Powers of Pascal

1 second
64 megabytes
Hard

The Pascal matrix is the (infinite) matrix defined by (zero based row and column):

Pascal[row, column] = Comb(row, column) \text{ for } 0 \le column \le row

and zero otherwise, where Comb(n, k) is the number of combinations of things taken at a time (the binomial coefficient).

For this problem, you will write a program to compute entries in powers of the Pascal matrix:

Pascal^P = Pascal \times Pascal \times \ldots \times Pascal

( factors)

Since the matrix is lower triangular, all powers are lower triangular and only the upper left by corner is used in computing coefficients in the upper left by corner of the power.

Input

The first line contains the number of data sets (1 \le k \le 1000) that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input containing four space-separated decimal integers. The first integer is the data set number. The second integer is the power (1 \le p \le 100000), to which to raise the Pascal matrix. The third and fourth integers give the row number and the column number (0 \le c \le r \le 100000) of the desired entry.

Output

For each data set there is a single line of output. The line consists of the data set number, a single space, which is then followed by the requested entry of the requested Power of the Pascal matrix. Input values will be restricted so results will not overflow a -bit integer value.

Examples

Example 1

Loading
Loading