Có \(Q\) truy vấn, mỗi truy vấn yêu cầu tính \(C_{n_i}^{k_i} \pmod{p}\) với cùng một \(p\) nguyên tố. Hay trả lời tất cả các truy vấn.

Định dạng đầu vào

• Dòng đầu: hai số nguyên \(Q, p\) (\(1 \le Q \le 10^5\), \(p \le 10^5\), \(p\) nguyên tố).
• \(Q\) dòng tiếp: mỗi dòng chứa hai số \(n_i, k_i\) (\(0 \le k_i \le n_i \le 10^{18}\)).

Định dạng đầu ra

• \(Q\) dòng, mỗi dòng là \(C_{n_i}^{k_i} \bmod p\).

Ví dụ

Input:

2 7
10 3
5 2

Output:

1
3

Ràng buộc

• 100% số điểm: \(p \le 10^5\), \(Q \le 10^5\).