Under construction

Still being built. Things may change

Binomial coefficient 6

Time limit2sMemory limit512 MB

Summary
For up to 100,000 queries, compute the binomial coefficient C(N,K) modulo 142857 where N goes up to 1e9.
Level

Hard8 of 10

Topics
Number theory, Combinatorics, Math
Solved
No attempts yet

Problem

You are given a positive integer NN and an integer KK. Write a program that computes the remainder of the binomial coefficient (NK)\binom{N}{K} divided by 142857142857.

Input

The first line contains the number of test cases TT. (1≤T≤1051 \le T \le 10^5)

Each of the next TT lines holds one test case, with NN and KK separated by a space. (1≤N≤1091 \le N \le 10^9, 0≤K≤N0 \le K \le N)

Output

For each test case, print the remainder of (NK)\binom{N}{K} divided by 142857142857 on its own line.

Examples4

  1. Example 1

    Input
    4
2 1
4 0
5 2
10 3
    Expected output
    2
1
10
120

  2. Example 2

    Input
    2
1 0
1 1
    Expected output
    1
1

  3. Example 3

    Input
    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
    Expected output
    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. Example 4

    Input
    8
24 12
25 12
26 13
27 13
30 15
40 20
50 25
60 30
    Expected output
    132730
57448
114896
58320
117675
95238
134199
132682