Decode Ways

You are given an encoded message containing digits. Each digit or pair of digits can be mapped to a letter using the mapping (A \to 1, B \to 2, \ldots, Z \to 26). For example, the string "12" can be decoded as "AB" (1 2) or "L" (12), so there are 2 ways. Your task is to compute the total number of ways to decode a given non-empty string. Note that a substring starting with '0' is not valid. (dp[i] = dp[i-1] \text{ if the last digit is valid}) plus (dp[i-2] \text{ if the last two digits form a number between 10 and 26}).

inputFormat

The input is provided from standard input (stdin) as a single line containing a string of digits representing the encoded message.

outputFormat

Print to standard output (stdout) a single integer representing the total number of ways to decode the given message.## sample

12

2