Tổ hợp (Version 2)

Xem PDF

Điểm: 450 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên \(P\) có dạng như sau:
\(P\) \(=\) \({p_1}^{e_1} . {p_2}^{e_2} .\) ... \(. {p_k}^{e_k}\) , sao cho với \(\forall i, 1 \leq i \leq k\), \(p_i\) là số nguyên tố, \(e_i \geq 1\)\({p_i}^{e_i} \leq 2.10^5\)

Cho \(T\) truy vấn, mỗi truy vấn gồm hai số \(N, K\) \((K \leq N)\). Với mỗi truy vấn, bạn hãy tính \(\binom{N}{K}\) \(mod\) \(P\).

Input

  • Dòng đầu tiên chứa \(2\) số nguyên dương \(T, P\) \((T \leq 10^4)\) lần lượt là số lượng truy vấn và số cho trước.
  • \(T\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(N, K\).

Output

  • Với mỗi truy vấn, in ra một số nguyên là đáp số của truy vấn đó.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N, K \leq 10^3\); \(P \leq 10^9\).
  • Subtask \(2\) (\(20\%\) số điểm): \(N, K \leq 10^5\); \(P \leq 2.10^5\), \(P\) là số nguyên tố.
  • Subtask \(3\) (\(20\%\) số điểm): \(N, K \leq 10^5\); \(P \leq 10^9\).
  • Subtask \(4\) (\(30\%\) số điểm): \(N, K \leq 10^9\); \(P \leq 10^9\).

Example

Test 1

Input
3 8
7 4
6 3
5 2
Output
3
4
2
Note
  • \(\binom{N}{K}\) là tổ hợp chập \(K\) của \(N\).

Bình luận

Không có bình luận nào.