Cho \(n\) và \(p\) nguyên tố. Tính tổng: \(S = \sum_{k=0}^{n} C_n^k \bmod 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 7

Output:

4

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

Ràng buộc

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