A message of uppercase letters was encoded to digits with the mapping 1 -> A, 2 -> B, ..., 26 -> Z, and the digits were concatenated with no separators. Given the digit string, count how many distinct original letter messages could produce it.
A leading zero in any group is invalid (there is no code 0, and codes like 06 are not allowed), so some inputs decode in zero ways.
Input format
A single line: a non-empty string of digits 0-9.
Output format
A single integer: the number of valid decodings.
Constraints
- 1 <= length of the digit string <= 1000
- The answer fits in a signed 64-bit integer for every test.