Tổ hợp Ckn 1

Xem PDF



Tác giả:
Dạng bài
Điểm: 2200 (p) Thời gian: 1.5s 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 \(p\)

Input

  • Dòng \(1\) chứa \(2\) số nguyên \(t\) \((t \leq 10^4)\) là số test và \(p\) là modulo , cách bởi \(1\) dấu cách.
  • \(t\) dòng tiếp theo chứa \(2\) số nguyên \(n\)\(k\) \((n, k \leq 10^{16})\)

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.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(p = 100003\)
  • Subtask \(2\) (\(50\%\) số điểm): \(p = 987654321\)

Example

Test 1

Input
2 100003
3 3
3 2
Output
1
3

Test 2

Input
2 987654321
3 3
3 2
Output
1
3

Bình luận