Giải Mã Tin Nhắn

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một tin nhắn gồm các chữ cái in hoa 'A' đến 'Z' được mã hóa thành chuỗi chữ số theo quy tắc: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.

Cho một chuỗi chữ số $S$ có độ dài $N$. Hãy đếm số cách giải mã chuỗi $S$ thành chuỗi chữ cái ban đầu. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.

Lưu ý: '0' không thể đứng một mình (ví dụ '06' không hợp lệ). Nếu không có cách giải mã nào, in ra 0.

Dữ liệu vào
  • Một dòng duy nhất chứa chuỗi $S$ chỉ gồm các chữ số '0'..'9' ($1 \le |S| \le 10^5$).
Dữ liệu ra
  • In ra số cách giải mã modulo $10^9 + 7$.
Ví dụ
Input Output
12 2
226 3
Giới hạn
  • $1 \le |S| \le 10^5$
Draft saved