Dynamic ProgrammingString
A message of digits can be decoded using the mapping A = 1, B = 2, ..., Z = 26. For example 11106 can be read as AAJF (1 1 10 6) or KJF (11 10 6). A 0 can only appear as part of 10 or 20. Count the number of ways to decode the string.
Input
A single string of digits.
Output
Print the number of ways (0 if it cannot be decoded).
Constraints
1 <= length <= 40
Example 1
Input
12
Output
2
AB (1 2) or L (12).
Example 2
Input
226
Output
3
BZ, VF and BBF.
Example 3
Input
06
Output
0
A leading 0 cannot be decoded.