Tổ hợp Ckn 3

Xem PDF

Đ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


  • 1
    flo    11:45 a.m. 18 Tháng 9, 2023

    wait what?