Message Decoding Ways

You are given an encoded message containing digits. Each digit or pair of digits represents a letter: '1' corresponds to 'A', '2' to 'B', ..., '26' to 'Z'. Your task is to determine the total number of ways to decode the message. Note that the encoded message must follow these rules:

• An empty message returns 0.
• A message that starts with '0' is invalid and should return 0.
• The decoding follows the dynamic programming recurrence given by: $$dp[i] = \begin{cases} dp[i-1] & \text{if } s[i-1] \neq 0 \\ dp[i-2] & \text{if } 10 \leq \text{num}(s[i-2:i]) \leq 26 \end{cases}$$

The final answer is the value of $$dp[n]$$ where n is the length of the input string.

inputFormat

The input is a single line from standard input containing a non-negative string of digits representing the encoded message.

outputFormat

Output a single integer to standard output, which is the number of ways to decode the given message.

12

2