Điểm:
2500 (p)
Thời gian:
10.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tính tổ hợp chập \(k\) của \(n\) phần tử \(C_n^k\) hay \(\dbinom{n}{k}\) theo modulo số nguyên tố \(p\)
Input
- Dòng \(1\) chứa \(1\) số nguyên \(t\) \((t \leq 10^5)\) là số test.
- \(t\) dòng tiếp theo chứa \(3\) số nguyên \(n, p, k\) \((k < n < p \leq 10^{11})\)
- Test cases đảm bảo rằng \(p\) nguyên tố và tổng tất cả \(\sqrt{p} < 320000\)
Output
- Gồm \(t\) dòng, mỗi dòng là 1 số nguyên không âm là kết quả của test tương ứng.
Example
Test 1
Input
3
1000 500 9907
1000000 500000 9999907
10000000000 5000000000 99999999907
Output
5813
9124052
10234200651
Bình luận
wait what?