DIY: Decode Ways

Problem statement

A message containing the letters from A-Z can be encoded into a string of numbers, using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped and then mapped back into letters, using the reverse of the mapping above (there may be multiple ways of doing this). For example, "11203" can be mapped into:

• "AATC", with the grouping (1 1 20 3)
• "KTC", with the grouping (11 20 3)

Note that the grouping (1 12 03) is invalid because "03" cannot be mapped into "C" since "3" is different from "03".

Given a string s that contains only digits, you will return the number of ways that can be used to decode it.

Note: s contains only digits and may contain leading zero(s).

Input

The input will be a string. The following are examples of input to the function:

# Sample Input 1
"12"

# Sample Input 2
"0"

# Sample Input 3
"226"

# Sample Input 4
"08"

Output

The output will be an integer. The following are examples of the outputs of the function:

# Sample Output 1
2 

# Sample Output 2
0

# Sample Output 3
3

# Sample Output 4
0