Powers of Pascal
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
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 (0 ≤ c ≤ r ≤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 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.