Decode Ways

You are given a string representing an encoded message where each character is a digit. The encoding maps '1' to 'A', '2' to 'B', ..., '26' to 'Z'. Your task is to determine the total number of ways to decode the given message.

Note: The decoding process must consider that some segments may not correspond to any letter (for example, a segment starting with '0' is invalid).

In mathematical terms, if we denote by \( s \) the input string and \( dp[i] \) the number of ways to decode the substring \( s[0:i] \), then the recurrence is: \[ \begin{aligned} & dp[0] = 1,\\ & dp[1] = 1 \quad \text{if } s[0] \neq '0',\\ & dp[i] = \begin{cases} dp[i-1] & \text{if } 1 \leq s[i-1] \leq 9,\\ dp[i] + dp[i-2] & \text{if } 10 \leq \text{int}(s[i-2:i]) \leq 26. \end{cases} \end{aligned} \]

Your goal is to implement this decoding algorithm efficiently and output the number of decoded messages.

inputFormat

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

outputFormat

Output an integer representing the total number of ways the input message can be decoded.

12

2