const MOD int = 1000000007

func numDecodings(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[0] = 1
	switch s[0] {
	case '*':
		dp[1] = 9
	case '0':
		return 0
	default:
		dp[1] = 1
	}
	for i := 2; i <= n; i++ {
		if s[i-1] == '*' {
			dp[i] = 9 * dp[i-1] // blabla | *
			if s[i-2] == '1' || s[i-2] == '*' {
				dp[i] += 9 * dp[i-2] // blabla | 1*
			}
			if s[i-2] == '2' || s[i-2] == '*' {
				dp[i] += 6 * dp[i-2] // blabla | 2*
			}
		} else if s[i-1] != '0' {
			dp[i] = dp[i-1]
			if s[i-2] == '1' || s[i-2] == '*' {
				dp[i] += dp[i-2] // blabla | 17
			}
			if s[i-1] < '7' && (s[i-2] == '2' || s[i-2] == '*') {
				dp[i] += dp[i-2] // blabla | 26
			}
		} else {
			if s[i-2] == '1' || s[i-2] == '*' {
				dp[i] += dp[i-2] // blabla | 10
			}
			if s[i-2] == '2' || s[i-2] == '*' {
				dp[i] += dp[i-2] // blabla | 20
			}
		}
		dp[i] %= MOD
	}
	return dp[n]
}