Number of Decoding Ways

You are given a non-empty string s containing only digits. Your task is to determine the number of ways to decode this string into letters using the following mapping:

\(1 \to A,\ 2 \to B,\ \ldots,\ 26 \to Z\)

Each digit or a pair of digits must correspond to a letter. For example, the string "12" can be decoded as "AB" (1 2) or "L" (12), hence there are 2 ways.

Constraints:

• 1 \(\leq\) s.length \(\leq\) 100
• s contains only digits and does not contain leading zeros.

Read the input from stdin and write the output to stdout.

inputFormat

The input consists of a single line containing the string s which represents the encoded message.

Example:

226

outputFormat

Output a single integer representing the total number of possible decodings of the input string.

Example:

3

## sample

12

2

</p>