decodeWays

Bình nhận được một đoạn tin nhắn đã được mã hóa chỉ gồm các số từ 0 đến 9. Biết tin nhắn ban đầu chỉ chứa các ký tự viết hoa từ 'A' tới 'Z' và được mã hóa như sau:

'A' -> 1
'B' -> 2
'C' -> 3
...
'Z' -> 26

Với cách mã hóa này thì không thể giải mã được về tin nhắn ban đầu. Hãy viết hàm trả về số tin nhắn ban đầu có thể có.

Kết quả có thể rất lớn nên chỉ cần output ra kết quả sau khi chia dư cho 1000000007 (10^9 + 7)

Ví dụ

Cho s = "123", output sẽ có dạng decodeWays(s) = 3.
Giải thích: tin nhắn ban đầu có thể là "ABC", "LC", "AW".
Cho s = "40", output sẽ có dạng decodeWays(s) = 0.
Giải thích: Không tồn tại một tin nhắn nào mà sau khi mã hóa ra được "40"

Đầu vào/Đầu ra