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\) và \(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

2 100003
3 3
3 2

1
3

2 987654321
3 3
3 2

1
3