Giải Mã Tin Nhắn
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion