시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 19 18 66.667%

문제

파스칼 행렬은 크기가 무한대이며 다음과 같이 정의한다. (행과 열 번호는 0부터 시작한다)

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

위의 경우를 제외한 곳은 모두 0이다. Comb(n, k)는 조합이다.

1 0 0 0 0 0 0 0 0 0 ...
1 1 0 0 0 0 0 0 0 0 ...
1 2 1 0 0 0 0 0 0 0 ...
1 3 3 1 0 0 0 0 0 0 ...
1 4 6 4 1 0 0 0 0 0 ...
1 5 10 10 5 1 0 0 0 0 ...
1 6 15 20 15 6 1 0 0 0 ...
1 7 21 35 35 21 7 1 0 0 ...
1 8 28 56 70 56 28 8 1 0 ...
1 9 36 84 126 126 84 36 9 1 ...
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

파스칼 행렬의 제곱을 구하는 프로그램을 작성하시오.

PascalP = Pascal × Pascal × ... × Pascal

입력

첫째 줄에 테스트 케이스의 개수 K (1 ≤ K ≤ 1000)가 주어진다.

각 테스트 케이스는 네 정수로 이루어져 있다. 첫 번째 정수는 테스트 케이스 번호이다. 두 번째 정수는 P이다. (1 ≤ P ≤ 100,000) 세 번째 정수와 네 번째 정수는 R과 C이다. (0 ≤ C ≤ R ≤ 100,000)

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고, PascalP의 R행 C열의 값을 출력한다. 답이 64비트 정수 범위를 넘어가지 않는 입력만 주어진다.

예제 입력

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

예제 출력

1 56
2 8759577256290
3 199998000000000

힌트