new_contents: # Time:  O(n)
  # Space: O(1)
  
  # A message containing letters from A-Z is being encoded to numbers using the following mapping way:
  #
  # 'A' -> 1
  # 'B' -> 2
  # ...
  # 'Z' -> 26
  # Beyond that, now the encoded string can also contain the character '*',
  # which can be treated as one of the numbers from 1 to 9.
  #
  # Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
  #
  # Also, since the answer may be very large, you should return the output mod 109 + 7.
  #
  # Example 1:
  # Input: "*"
  # Output: 9
  # Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
  # Example 2:
  # Input: "1*"
  # Output: 9 + 9 = 18
  # Note:
  # The length of the input string will fit in range [1, 105].
  # The input string will only contain the character '*' and digits '0' - '9'.
  
  class Solution(object):
      def numDecodings(self, s):
          """
          :type s: str
          :rtype: int
          """
          M, W = 1000000007, 3
          dp = [0] * W
          dp[0] = 1
          dp[1] = 9 if s[0] == '*' else dp[0] if s[0] != '0' else 0
          for i in xrange(1, len(s)):
              if s[i] == '*':
                  dp[(i + 1) % W] = 9 * dp[i % W]
                  if s[i - 1] == '1':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + 9 * dp[(i - 1) % W]) % M
                  elif s[i - 1] == '2':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + 6 * dp[(i - 1) % W]) % M
                  elif s[i - 1] == '*':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + 15 * dp[(i - 1) % W]) % M
              else:
                  dp[(i + 1) % W] = dp[i % W] if s[i] != '0' else 0
                  if s[i - 1] == '1':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + dp[(i - 1) % W]) % M
                  elif s[i - 1] == '2' and s[i] <= '6':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + dp[(i - 1) % W]) % M
                  elif s[i - 1] == '*':
                      dp[(i + 1) % W] = (dp[(i + 1) % W] + (2 if s[i] <= '6' else 1) * dp[(i - 1) % W]) % M
          return dp[len(s) % W]
  
subject: Create decode-ways-ii.py