Lò Cò (hay cò 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ó ả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 đơn vị độ dài, 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ị, 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 trước 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 phần dư của k chia m.

Dữ liệu: Cho từ tệp văn bản LOCO.INP chỉ có một dòng chứa hai số nguyên dương n, m (n ≤ 10^15; m <2019), giữa hai số cách nhau một khoảng cách.

Kết quả: Ghi ra tập văn bản LOCO.OUT chỉ có một dòng chứa số nguyên là phần dư của k chia cho m.

Input:

5 100

Output:

13

Ràng buộc:

• Có 60% số test tương ứng với 60% số điểm có 1< n ≤ 20;

• Có 30% số test tương ứng với 30% số điểm có 20< n ≤ 10^6;

• Có 10% số test tương ứng với 10% số điểm có 10^6< n ≤ 10^15