class Solution {
    private final int MOD = 1000000007;

    public int numDecodings(String s) {
        char[] chs = s.toCharArray(); // '*' means 1~9
        if (chs[0] == '0') return 0;
        int[] dp = new int[chs.length + 1];
        dp[0] = 1;
        dp[1] = chs[0] == '*' ? 9 : 1;
        for (int i = 2; i <= chs.length; i++) {
            char curr = chs[i - 1], prev = chs[i - 2];
            long val = 0;
            if (curr == '*') { // Warning: overflow!
                val = 9L * dp[i - 1]; // blabla | *
                if (prev == '1' || prev == '*')
                    val += 9L * dp[i - 2]; // blabla | 1*
                if (prev == '2' || prev == '*')
                    val += 6L * dp[i - 2]; // blabla | 2*
            } else if (curr == '0') {
                if (prev == '1' || prev == '*')
                    val += dp[i - 2]; // blabla | 10
                if (prev == '2' || prev == '*')
                    val += dp[i - 2]; // blabla | 20
            } else {
                val = dp[i - 1]; // blabla | curr
                if (prev == '1' || prev == '*')
                    val += dp[i - 2]; // blabla | 1curr
                if ((prev == '2' || prev == '*') && curr <= '6')
                    val += dp[i - 2]; // blabla | 2curr
            }
            dp[i] = (int) (val % MOD);
        }
        return dp[chs.length];
    }
}