Tính tổ hợp \(C_n^k\) modulo \(p\), trong đó \(p\) là một số nguyên tố nhỏ (\(p \le 10^5\)). Tuy nhiên \(n, k\) có thể rất lớn (\(n \le 10^{18}\)).

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

• Một dòng chứa ba số nguyên \(n, k, p\) (\(0 \le k \le n \le 10^{18}\), \(p \le 10^5\), \(p\) nguyên tố).

Định dạng đầu ra

• Một số nguyên là \(C_n^k \bmod p\).

Ví dụ

Input:

10 3 7

Output:

1

Giải thích: \(C_{10}^3 = 120 = 17 \times 7 + 1 \equiv 1 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(n, k \le 10^{18}\), \(p \le 10^5\) nguyên tố.