Decode Ways

A message in capital letters is turned into digits using A = 1, B = 2 and so on up to Z = 26, with the numbers written one after another and no gaps. Reading it back can be ambiguous: "15" could mean "AE" or "O".

Write count_decodings(digits) that returns how many different messages could have produced digits. A piece can never start with 0 ("06" is not a letter, while "10" and "20" are), so some digit strings cannot be decoded at all: return 0 for those.

Examples

count_decodings("1123")  # returns 5
count_decodings("2101")  # returns 1
count_decodings("30")    # returns 0

"1123" can be read as 1 1 2 3, 11 2 3, 1 12 3, 1 1 23 or 11 23: five messages.

Constraints

• 1 <= len(digits) <= 100
• digits contains only the characters 0 to 9
• The answer can be very large