# Python program to count decoding ways of a digit string
# using Tabulation
 
# Function to count decoding ways for the entire string.
def countWays(digits):
    n = len(digits)
 
    # Create a dp list initialized to 0, with size n + 1.
    dp = [0] * (n + 1)
 
    # Base case: An empty string has one valid decoding.
    dp[n] = 1
 
    # Iterate from the end of the string to the beginning.
    for i in range(n - 1, -1, -1):
 
        # Single-digit decoding: check if current
        # digit is not '0'.
        if digits[i] != '0':
            dp[i] = dp[i + 1]
 
        # Two-digit decoding: check if next two digits are valid.
        if (i + 1 < n and
            ((digits[i] == '1' and digits[i + 1] <= '9') or
             (digits[i] == '2' and digits[i + 1] <= '6'))):
            dp[i] += dp[i + 2]
 
    return dp[0]
 
 
if __name__ == "__main__":
 
    digits = "12123232323232223333"
 
    print(countWays(digits))

IyBQeXRob24gcHJvZ3JhbSB0byBjb3VudCBkZWNvZGluZyB3YXlzIG9mIGEgZGlnaXQgc3RyaW5nCiMgdXNpbmcgVGFidWxhdGlvbgoKIyBGdW5jdGlvbiB0byBjb3VudCBkZWNvZGluZyB3YXlzIGZvciB0aGUgZW50aXJlIHN0cmluZy4KZGVmIGNvdW50V2F5cyhkaWdpdHMpOgogICAgbiA9IGxlbihkaWdpdHMpCgogICAgIyBDcmVhdGUgYSBkcCBsaXN0IGluaXRpYWxpemVkIHRvIDAsIHdpdGggc2l6ZSBuICsgMS4KICAgIGRwID0gWzBdICogKG4gKyAxKQoKICAgICMgQmFzZSBjYXNlOiBBbiBlbXB0eSBzdHJpbmcgaGFzIG9uZSB2YWxpZCBkZWNvZGluZy4KICAgIGRwW25dID0gMQoKICAgICMgSXRlcmF0ZSBmcm9tIHRoZSBlbmQgb2YgdGhlIHN0cmluZyB0byB0aGUgYmVnaW5uaW5nLgogICAgZm9yIGkgaW4gcmFuZ2UobiAtIDEsIC0xLCAtMSk6CgogICAgICAgICMgU2luZ2xlLWRpZ2l0IGRlY29kaW5nOiBjaGVjayBpZiBjdXJyZW50CiAgICAgICAgIyBkaWdpdCBpcyBub3QgJzAnLgogICAgICAgIGlmIGRpZ2l0c1tpXSAhPSAnMCc6CiAgICAgICAgICAgIGRwW2ldID0gZHBbaSArIDFdCgogICAgICAgICMgVHdvLWRpZ2l0IGRlY29kaW5nOiBjaGVjayBpZiBuZXh0IHR3byBkaWdpdHMgYXJlIHZhbGlkLgogICAgICAgIGlmIChpICsgMSA8IG4gYW5kCiAgICAgICAgICAgICgoZGlnaXRzW2ldID09ICcxJyBhbmQgZGlnaXRzW2kgKyAxXSA8PSAnOScpIG9yCiAgICAgICAgICAgICAoZGlnaXRzW2ldID09ICcyJyBhbmQgZGlnaXRzW2kgKyAxXSA8PSAnNicpKSk6CiAgICAgICAgICAgIGRwW2ldICs9IGRwW2kgKyAyXQoKICAgIHJldHVybiBkcFswXQoKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CgogICAgZGlnaXRzID0gIjEyMTIzMjMyMzIzMjMyMjIzMzMzIgoKICAgIHByaW50KGNvdW50V2F5cyhkaWdpdHMpKQ==