Submit solution

Points: 1.31 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Nguyễn Duy Khánh
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.