Decoding Ways

You are given a string message consisting only of digits. This string represents an encoded message using the mapping \( '1' \to 'A', '2' \to 'B', \dots, '26' \to 'Z' \). Your task is to compute the number of ways to decode the message.

The decoding follows the rules:

• If the message is empty or starts with a '0', the output is \(0\).
• You can decode one digit if it is between 1 and 9.
• You can decode two digits if the number formed is between 10 and 26 (i.e., \(10 \leq \text{number} \leq 26\)).

The solution should use a dynamic programming approach where \(dp[i]\) represents the number of ways to decode the first \(i\) characters of the message. The recurrence is as follows:

[ \begin{align*} dp[0] &= 1,\ dp[1] &= 1 \quad \text{if } message[0] \neq '0',\ \text{for } i \ge 2:\quad dp[i] &= \begin{cases} dp[i-1] & \text{if single digit is valid}\ dp[i-1] + dp[i-2] & \text{if two-digit number is valid (i.e. } 10 \leq \text{number} \leq 26 \text{)} \end{cases} \end{align*} ]

Print the total number of valid decodings to the standard output.

inputFormat

A single line containing a string of digits representing the encoded message. Read the input from standard input (stdin).

outputFormat

Print a single integer representing the number of valid decodings for the message to standard output (stdout).## sample

123

3