이항 계수 6

자연수 $N$과 정수 $K$가 주어진다. 이항 계수 $\binom{N}{K}$를 $142857$로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^5$)

다음 $T$개 줄에 테스트 케이스가 한 줄씩 주어진다. 각 줄에는 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^9$, $0 \le K \le N$)

각 테스트 케이스마다 $\binom{N}{K}$를 $142857$로 나눈 나머지를 한 줄에 하나씩 출력한다.