Decode Ways

You are given a string s consisting of digits. Your task is to determine the number of ways to decode the string to letters using the mapping:

$$ 'A' \to 1,\ 'B' \to 2, \dots, 'Z' \to 26 $$

Note that if the string contains invalid sequences (for instance, numbers with a leading zero), there is no valid decoding for that part. The answer must be computed modulo $$10^9+7$$.

For example, the string "12" can be decoded as "AB" (1 2) or "L" (12).

inputFormat

The input is provided via stdin and consists of a single line containing the string s made up of digits.

outputFormat

Output a single integer denoting the total number of ways to decode the string, computed modulo $$10^9+7$$, to stdout.

12

2