Decode Ways

Letters are encoded as numbers: A → 1, B → 2, …, Z → 26. Given a string of digits, in how many ways can it be decoded back into letters? For example 226 → BZ (2 26), VF (22 6) or BBF (2 2 6) → 3 ways. A code can't start with 0 (06 is not F). Print the count modulo 1 000 000 007.

Input: one line of digits.

Output: the number of decodings modulo 10⁹ + 7 (0 if it can't be decoded at all).

Constraints: 1 ≤ length ≤ 10⁵.

Think about it: like climbing stairs with rules: the last step is either one digit (if it isn't 0) or two digits (if they form 10–26). ways[i] = ways[i−1]·[one-digit ok] + ways[i−2]·[two-digit ok].