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

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

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

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

PascalP = Pascal × Pascal × ... × Pascal

입력 형식

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

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

출력 형식

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

예제 입력

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

예제 출력

1 56
2 8759577256290
3 199998000000000