Decode Ways

You are given a string s representing an encoded message containing only digits. The encoding is done by mapping each letter to a number: 'A' is 1, 'B' is 2, ..., and 'Z' is 26. For example, "12" can be decoded as "AB" (1 2) or "L" (12).

Your task is to determine the total number of ways to decode the message. Note that the decoding must adhere to the following rules:

• A single digit between 1 and 9 can be decoded as a letter.
• A pair of digits, forming a number between 10 and 26 (i.e. $$10 \leq number \leq 26$$), can be decoded as a letter.
• A digit '0' on its own does not correspond to any letter.

If the input string is empty or cannot be segmented into valid decodings, return 0.

This problem can be solved efficiently using dynamic programming.

inputFormat

The input consists of a single line containing a non-negative integer string s representing the encoded message.

Example:

12

outputFormat

Output a single integer denoting the total number of ways to decode the input message.

Example:

2

## sample

12

2