Decode Ways
Letters are encoded as A=1, B=2, …, Z=26. Given a string of digits, count the ways to decode it (modulo ). 12 → AB or L (2 ways). 06 can't be decoded (0 ways).
Input
One string of digits.
Output
The number of decodings modulo 1000000007.
Constraints
1 to digits.
Sample 1
Input
12
Output
2
Sample 2
Input
226
Output
3