Count Decodings

You are given a string s consisting of digits. Each digit or pair of digits may represent a letter according to the mapping: 1 → A, 2 → B, ..., 26 → Z. Your task is to compute the number of distinct ways to decode the entire string into a sequence of letters.

Note: A leading zero is not allowed, and the two-digit number must be in the range $$10 \leq x \leq 26$$ to be considered valid for decoding. If the string is empty, it is considered to have one valid decoding.

For example, the string "12" can be decoded as "AB" (1 2) or "L" (12), resulting in 2 valid decodings.

inputFormat

The input consists of a single line that contains the digit string s. The string will contain only characters from '0' to '9'.

outputFormat

Output a single integer which is the number of ways to decode the given string.

12

2