Cho số nguyên tố \(p\) và số nguyên dương \(n\). Tính tổng: \(S = C_n^0 + C_n^p + C_n^{2p} + C_n^{3p} + \dots \bmod p\) (tổng các tổ hợp với chỉ số là bội của \(p\)).

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

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

Định dạng đầu ra

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

Ví dụ

Input:

5 3

Output:

2

Giải thích: \(C_5^0 + C_5^3 = 1 + 10 = 11 \equiv 2 \pmod{3}\).

Ràng buộc

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