Tính \(C_n^k \mod m\).

Input

• Dòng đầu tiên chứa số \(T\), là số lượng test.

• \(T\) dòng tiếp theo mỗi dòng chứa ba số \(n, k, m\) (\(1 \le n \le 10^5, 0 \le k \le n, 2 \le m \le 10^9\)).

Output

• Ghi ra \(T\) dòng tương ứng với kết quả của từng test.

Example

5
11 11 100
14 10 1000
14 4 10000
13 0 100000
12 11 1000000

1
1
1001
1
12