Number of Ways to Decode

You are given an encoded message containing only digits. The encoding follows the mapping: \( A \to 1, B \to 2, \ldots, Z \to 26 \). Your task is to determine the total number of ways to decode the given message.

For example, the string "12" can be decoded as "AB" (1 2) or "L" (12), and hence has 2 possible decodings.

Note that the encoded message may contain leading or embedded zeros which are not valid unless they follow a valid prefix (like "10" or "20"). An empty string is considered to have 0 decodings.

Constraints: The input string consists only of digits and may be up to moderate length.

inputFormat

A single line is read from standard input, containing the encoded message as a string of digits.

outputFormat

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

12

2