Decode Ways

You are given an encoded message containing digits. Each digit or valid two-digit number (from 10 to 26) can be mapped to a letter using the mapping: \( A\to1,\ B\to2,\ldots,\ Z\to26 \). For example, the string "12" can be decoded as "AB" (1, 2) or "L" (12).

Your task is to determine the total number of ways to decode the message. A dynamic programming approach is recommended, where the recurrence relation is given by:

\[ \text{dp}[i]=\begin{cases} \text{dp}[i-1] & \text{if } s[i-1] \neq '0' \\ +\;\text{dp}[i-2] & \text{if } 10 \leq s[i-2:i] \leq 26 \end{cases} \]
Note that the input string may contain leading zeroes which are not decodable. An empty string is considered to have 0 decoding ways.

inputFormat

The input consists of a single line containing a non-negative integer string representing the encoded message.

outputFormat

Output a single integer, the total number of ways to decode the given message.## sample

1

1