class Solution {public:    int numDecodings(string s) {        int n = s.length();        if (n == 0) return 0;        vector
     
       dp(n+1, 0);        dp[0] = 1;        for (int i = 0; i < n; i++) {            if (s[i] == '*') {                dp[i+1] += dp[i] * 9;                if (i > 0) {                    if (s[i-1] == '*' || s[i-1] == '1')                        dp[i+1] += dp[i-1] * 9;                    if (s[i-1] == '*' || s[i-1] == '2')                        dp[i+1] += dp[i-1] * 6;                }            }            else {                if (s[i] != '0')                    dp[i+1] += dp[i];                if (i > 0) {                    if (s[i-1] == '*' || s[i-1] == '1')                        dp[i+1] += dp[i-1];                    if ((s[i-1] == '*' || s[i-1] == '2') && s[i] <= '6')                        dp[i+1] += dp[i-1];                }            }            dp[i+1] %= 1000000007;        }        return dp[n];    }};