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×p + n2×p² + ... + nr×p^r k = k0 + k1×p + k2×p² + ... + kr×p^r

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

Lưu ý: C(ni, ki) = 0 nếu ki > ni.

Đầu vào

Một dòng duy nhất chứa ba số nguyên n, k, p (0 ≤ k ≤ n ≤ 10^18, 1 < p ≤ 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 mod 7 = 1.