Submit solution
Points:
1.31 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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