Sau khi được đố câu hỏi Violympic: "Có bao nhiêu số lẻ có ~6~ chữ số, các chữ số đứng cạnh nhau thì khác nhau", Songuku95 nghĩ ra một bài toán mở rộng hơn:

Cho ~2~ số tự nhiên ~N~, ~M~. Tập hợp ~A = \{0, 1, 2, \dots, n\}~. Câu hỏi đặt ra là có bao nhiêu dãy ~X~ gồm ~k~ phần tử: ~\{x_1, x_2, x_3, \dots, x_k\}~ thỏa mãn:

• ~X_i~ thuộc tập hợp ~A~ ~(1 \le i \le k)~
• ~X_k~ là số lẻ
• ~X_1~ khác ~0~
• ~X_i~ và ~X_{i + 1}~ là ~2~ số khác nhau (với ~1 \le i < k)~
• ~1 \le k \le N~

Do kết quả có thể rất lớn nên các bạn chỉ cần in ra Kết quả mod ~M~.

Lưu ý: ~2~ dãy ~X~, ~Y~ khác nhau nếu tồn tại ~1~ vị trí ~p~ sao cho ~X_p~ khác ~Y_p~

Input

Gồm ~1~ dòng duy nhất chứa hai số ~N~, ~M~ ~(3 \le N~, ~M \le 10^{15})~

Output

Gồm 1 dòng duy nhất là kết quả bài toán

Giới hạn

• ~20\%~ số test có ~n~, ~m \le 1000~
• ~20\%~ số test tiếp theo có ~n~, ~m \le 10^{6}~
• ~20\%~ số test tiếp theo có ~n \le 10^{6}~, ~m \le 10^{15}~
• ~20\%~ số test tiếp theo có ~n \le 10^{15}~, ~m \le 1000~
• ~20\%~ số test còn lại có ~n~, ~m \le 10^{15}~

Sample Input

3 123456

Sample Output

20

Note

Có ~20~ số thỏa mãn là: ~1, 3, 13, 21, 23, 31, 101, 103, 121, 123, 131, 201, 203, 213, 231, 301, 303, 313, 321, 323~