Số cách giải mã xâu số

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Một thông điệp gồm các chữ cái in hoa từ 'A' đến 'Z' được mã hóa thành xâu chữ số theo quy tắc: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.

Cho một xâu chỉ gồm các chữ số '0'..'9' có độ dài $N$. Hãy đếm số cách giải mã hợp lệ xâu đó thành các chữ cái (lưu ý '06' không hợp lệ cho 'F', chỉ '6' mới hợp lệ). Kết quả lấy modulo $10^9 + 7$.

Dữ liệu vào
  • Một dòng duy nhất chứa xâu chữ số $S$ ($1 \le |S| \le 10^5$).
Dữ liệu ra

Một số nguyên duy nhất là số cách giải mã hợp lệ modulo $10^9 + 7$.

Ví dụ
Input Output
226 3
Giới hạn
  • $1 \le |S| \le 10^5$
Draft saved