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

3
1000 500 9907
1000000 500000 9999907
10000000000 5000000000 99999999907

5813
9124052
10234200651