Lò cò là một trò chơi dân gian, được cho là đã có từ thời La Mã cổ đại, rất thông dụng và có hình ảnh minh họa trên các giáo đường. Trò chơi này rèn luyện người chơi tập trung giữ thăng bằng, nâng cao sự khéo léo và tính toán, cụ thể: người chơi cần vượt qua một đoạn đường có \(n\) độ dài đơn vị, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là \(1\) đơn vị, \(2\) đơn vị và \(3\) đơn vị. Một cách di chuyển đúng là dãy các bước nhảy có tổng đúng bằng \(n\).

Yêu cầu:

• Cho \(n\) và \(m\), gọi \(k\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường dài \(n\) đơn vị. Hãy tính \(k \mod m\).

Input

• Đọc từ file văn bản LOCO.INP có dạng:
• Gồm 1 dòng chứa hai số \(n\) và \(m\) \((n \le 10^{15}; m \le 2019)\).

Output

• Đáp án thỏa đề.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^6\)
• Subtask \(3\) (\(10\%\) số điểm): không ràng buộc gì thêm.

Example

5 100

13