Ways to decode

A message of capital letters was turned into digits with A = 1, B = 2, …, Z = 26, and the numbers were written one after another with no spaces. Given the digits s, return the number of different ways to read them as letters.

decode_ways("226")    # 3: 2 2 6, 22 6, 2 26
decode_ways("10")     # 1: only 10 (J)
decode_ways("06")     # 0: 06 is not a letter

• A letter is 1 to 9 (one digit) or 10 to 26 (two digits). A 0 can only be the second digit of 10 or 20.
• The count can have thousands of digits. Return the remainder after dividing it by 1,000,000,007: count % 1_000_000_007. You may take the remainder after every addition; the result is the same.

Limits

• s has 1 to 100,000 digits.
• Python stops at about 1,000 nested calls, and a function wrapped in functools.cache stops after a few hundred in the browser. The big tests need far more than that, so memoised recursion fails them. Fill a table with a loop (lesson 3).