만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이항 계수 6

시간 제한2초메모리 제한512 MB

요약
최대 10만 개의 질의에 대해 N이 10억까지 주어질 때 이항계수 C(N,K)를 142857로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
정수론, 조합론, 수학
정답자
아직 제출이 없습니다

문제

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

입력

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

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

출력

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

예제4

  1. 예제 1

    입력
    4
2 1
4 0
5 2
10 3
    예상 출력
    2
1
10
120

  2. 예제 2

    입력
    2
1 0
1 1
    예상 출력
    1
1

  3. 예제 3

    입력
    54
1 0
1 1
2 0
2 1
2 2
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
    예상 출력
    1
1
1
2
1
1
3
3
1
1
4
6
4
1
1
5
10
10
5
1
1
6
15
20
15
6
1
1
7
21
35
35
21
7
1
1
8
28
56
70
56
28
8
1
1
9
36
84
126
126
84
36
9
1

  4. 예제 4

    입력
    8
24 12
25 12
26 13
27 13
30 15
40 20
50 25
60 30
    예상 출력
    132730
57448
114896
58320
117675
95238
134199
132682