Letters are sent as numbers: A = 1, B = 2, …, Z = 26, and the numbers are written one after another with no separators. Given the digit string, count how many different letter messages it could stand for. Codes never have leading zeros (06 is not a code).
Print the count modulo 1 000 000 007.
Constraints
- 1 ≤ length ≤ 100000
Input and output
- Input
- One line: a string of digits.
- Output
- One integer.
Examples
Input 1
226Output
3"2 2 6" = BBF, "22 6" = VF, "2 26" = BZ: 3 ways.
Input 2
06Output
0No letter has code 0 or 06, so 0 ways.
Show hints
- ways[i] counts the decodings of the first i digits.
- The last letter uses either one digit (1–9) or two digits (10–26).
Show the explanation
Let ways[0] = 1 and ways[i] be the number of decodings of the first i digits. The last letter uses either the single digit s[i−1] (allowed if it is not 0) — adding ways[i−1] — or the pair s[i−2..i−1] (allowed if it is 10–26) — adding ways[i−2]. Only the last two values are needed, so two variables suffice. Zeros are the edge case: a 0 can only be the second digit of 10 or 20.
Original UniCircle question. Last reviewed 22 Oct 2026.