shiba - bạn thân của _minhduc trong khi làm bài tập tết để vào ngày mùng tết cậu ấy có thể đi chơi thoải mái thì gặp một bài từ rất khó từ thầy giáo: Cho một số nguyên dương \(N\). Một dãy được gọi là dãy đẹp khi dãy đó là hoán vị của các số từ \(1\) đến \(N\) và dãy đó thỏa mãn rằng có ít nhất một cặp số liền kề trong dãy đó có dạng \((x,x+1)\). Ví dụ với \(N = 4\) thì các dãy \((1,2,4,3)\) và \((3,4,1,2)\) là các dãy đẹp, còn các dãy \((3,1,4,2)\) và \((4,3,2,1)\) thì không phải. shiba cần đếm số dãy đẹp khác nhau có thể tạo ra khi biết trước số nguyên dương \(N\).

Bài này khó đến nổi shiba không làm được. Cậu ấy chợt nhớ nhớ ra rằng _minhduc rất thông thạo về dãy hoán vị nên shiba đã hỏi bài bạn thân của mình. Nhưng _minhduc đang bận chơi game "bình nguyên vô tận" với bạn gái nên không thể chỉ bài cho shiba được vì sợ nếu bỏ trận đấu giữa chừng thì bạn gái của mình sẽ giận. Vì vậy _minhduc nhờ các bạn tài giỏi trong LQDOJ giải quyết bài toán này cho shiba ~rồi _minhduc sẽ lì xì cho các bạn :Đ~

Yêu cầu: Bạn hãy viết chương trình giải quyết bài toán trên sau khi chia lấy dư cho \(M\) với \(M\) là một số nguyên dương được nhập từ bàn phím.

Input

• Chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^{18}, 2 \le M \le 10^7)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(M\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 10\).

• Subtask \(2\) (\(20\%\) số điểm): Có \(N \le 15\).

• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 20\).

• Subtask \(4\) (\(30\%\) số điểm): Có \(N \le 10^6\).

• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 100

13