class Solution:
# 1 letter
# 0
# not * (dp[i] = dp[i + 1])
# * (dp[i] = 9 * dp[i + 1])
# 2 letter
# 0
# = 0
# 1
# [i + 1] != * (dp[i] = dp[i + 2])
# [i + 1] == * (dp[i] = 9 * dp[i + 2])
# 2
# [i + 1] == * (dp[i] = 6 * dp[i + 2])
# [i + 1] != * and [i + 1] in '0123456' (dp[i] = dp[i + 2])
# 3 - 9
# = 0
# *
# [i + 1] == * (dp[i] = 24 * dp[i + 2])
# [i + 1] != * and [i + 1] in '0123456' (dp[i] = 2 * dp[i + 2])
# [i + 1] != * and [i + 1] not in '0123456' (dp[i] = dp[i + 2])
def numDecodings(self, s: str) -> int:
MOD = 10 ** 9 + 7
dp = [0] * (len(s) + 1)
dp[-1] = 1
for i in range(len(s) - 1, -1, -1):
if s[i] == '0':
dp[i] = 0
elif s[i] == '*':
dp[i] = 9 * dp[i + 1] % MOD
if i + 1 < len(s):
if s[i + 1] == '*':
dp[i] += 15 * dp[i + 2] % MOD
elif s[i + 1] in '0123456':
dp[i] += 2 * dp[i + 2] % MOD
else:
dp[i] += dp[i + 2] % MOD
else:
dp[i] = dp[i + 1] % MOD
if i + 1 < len(s):
if s[i] == '1':
if s[i + 1] == '*':
dp[i] += 9 * dp[i + 2] % MOD
else:
dp[i] += dp[i + 2] % MOD
elif s[i] == '2':
if s[i + 1] == '*':
dp[i] += 6 * dp[i + 2] % MOD
elif s[i + 1] in '0123456':
dp[i] += dp[i + 2] % MOD
return dp[0] % MOD