파스칼 행렬의 거듭제곱

파스칼 행렬은 크기가 무한한 행렬이고, 행 번호와 열 번호는 0부터 센다. 각 원소는 다음과 같이 정의한다.

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

이 범위를 벗어난 자리는 모두 0이다. Comb(n, k)는 서로 다른 n개에서 k개를 고르는 조합의 수이다.

파스칼 행렬 $P$개를 곱한 행렬을 PascalP라고 하자.

PascalP = Pascal × Pascal × ... × Pascal

PascalP의 원소 하나를 구하는 프로그램을 작성하시오.

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

이어지는 $K$개 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄은 정수 네 개로 이루어진다. 첫 번째 정수는 테스트 케이스 번호이고, 두 번째 정수는 $P$ ($1 \leq P \leq 100000$), 세 번째와 네 번째 정수는 각각 $R$과 $C$이다 ($0 \leq C \leq R \leq 100000$).

각 테스트 케이스마다 테스트 케이스 번호와 PascalP의 $R$행 $C$열 값을 공백 하나로 구분해 한 줄에 출력한다.

답이 64비트 정수 범위를 넘지 않는 입력만 주어진다.