A message of digits is decoded using 1→A, 2→B, …, 26→Z. Count how many different ways the digit string can be decoded. Leading zeros are invalid.
1→A, 2→B, …, 26→Z
Input: one digit string. Output: the number of decodings.
Your program reads from stdin and prints to stdout.
Example 1
Input: 12
Output: 2
Hints