eolymp
bolt
Try our new interface for solving problems
Problems

Powers of Pascal

Powers of Pascal

Time limit 1 second
Memory limit 64 MiB

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

Pascal[row, column] = Comb(row, column) for 0 <= column <= row

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

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

Pascal^P = Pascal × Pascal × ... × Pascal (P factors)

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

Input data

The first line contains the number of data sets k (1 k 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 p (1 p 100000), to which to raise the Pascal matrix. The thrid and fourth integers give the row number r and the column number c (0cr100000) of the desired entry.

Output data

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 Powers of the Pascal matrix. Input values will be restricted so results will be restricted so results will not overflow a 64-bit integer value.

Examples

Input example #1
3
1 1 8 3
2 9 21 13
3 200 100000 99998
Output example #1
1 56
2 8759577256290
3 199998000000000
Source 2013 ACM Greater New York Region, October 27, Problem H