Decode Ways

You are given a string s containing only digits. The task is to determine the total number of ways to decode it into alphabetical letters, given the mapping of 1 → A, 2 → B, ..., 26 → Z.

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

Please note, an encoded message starting with the digit '0' is considered invalid. The decoding must follow the mapping which can be summarized using the formula:

$$dp[i] = \begin{cases} dp[i-1] &\text{if } s[i-1] \neq '0' \\ dp[i-1] + dp[i-2] &\text{if } 10 \leq s[i-2:i] \leq 26 \end{cases}$$

Implement a solution that computes the total number of ways to decode the given message. The input is provided via standard input and the output must be printed to standard output.

inputFormat

The input consists of a single line containing a non-empty string s composed of digits.

Example:

226

outputFormat

Output a single integer representing the total number of ways to decode the message.

Example:

3

## sample

12

2

</p>