Uma found an old ledger of stairwells in the bakery attic at the silver mines of Lodebarrow. The margin notes pose a precise question. Task: Digits encode letters: 1->A ... 26->Z. Print the number of ways to decode the digit string mod 1000000007. Input format: One line with a digit string s. Output format: Print the decode count mod 1000000007. Constraints: 1 <= |s| <= 1000; s contains digits 0-9.
Example 1:
Example 2:
Example 3:
Constraints:
1 <= |s| <= 1000; s contains digits 0-9.
