Tổ hợp chập \(C(n, k)\) là số cách chọn k phần tử từ n phần tử.

Cho hai số nguyên dương n, k và số nguyên tố p. Hãy tính \(C(n, k)\) mod p với p là số nguyên tố.

Sử dụng định lý Lucas: Biểu diễn n và k trong hệ cơ số p: n = n0 + n1\timesp + n2\timesp² + ... + nr\timesp^r k = k0 + k1\timesp + k2\timesp² + ... + kr\timesp^r

Khi đó: \(C(n, k)\) ≡ ∏ \(C(ni, ki)\) (mod p)

Lưu ý: \(C(n_i, k_i) = 0\) nếu \(k_i > n_i\).

Đầu vào

Một dòng duy nhất chứa ba số nguyên n, k, p (\(0 \le k \le n \le 10^{18}, 1 < p \le 10^6\), \(p\) là số nguyên tố).

Đầu ra

Một số nguyên duy nhất là \(C(n, k)\) mod p.

Ví dụ

Input:
10 3 7

Output:
1

Giải thích

\(C(10, 3) = 120, 120 \bmod 7 = 1\).

Ràng buộc & Subtasks