Decode the Message
Letters were encoded as A=1, ..., Z=26 and the numbers concatenated. Count the ways to decode the digit string, modulo 109+7 (0 if none).
Input: one line with a digit string.
Output: the number of decodings mod 109+7.
Constraints:
- 1 ≤ length ≤ 105
Sample Tests
Input 1
226
Output 1
3
Input 2
06
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.