A message containing letters fromA-Zis 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:

1. The length of the input string will fit in range [1, 10 5 ].
2. The input string will only contain the character '*' and digits '0' - '9'.

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;

        if (s.charAt(0) == '0') return 0;

        if (n >= 1){
            char c = s.charAt(0);
            if (c == '*') dp[1] = 9 ;
            else dp[1] = 1;
        }

        for (int i = 2; i <= n; i++){
            char char1 = s.charAt(i - 2);
            char char2 = s.charAt(i - 1);

            //System.out.println("i: " + i + " char1: " + char1 + " char2: " + char2);

            // handle 1 char
            if (char2 == '*'){
                dp[i] += dp[i - 1] * 9;
            }
            else if (char2 > '0'){
                dp[i] += dp[i - 1];
            }

            // handle 2 char
            if (char1 == '*'){
                if (char2 == '*'){
                    dp[i] += dp[i - 2] * 15;
                }
                else if (char2 <= '6'){
                    dp[i] += dp[i - 2] * 2;
                }
                else{
                    dp[i] += dp[i - 2];
                }
            }
            else if (char1 == '1' || char1 == '2'){
                if (char2 == '*'){
                    if (char1 == '1'){
                        dp[i] += dp[i - 2] * 9;
                    }
                    else{
                        dp[i] += dp[i - 2] * 6;
                    }
                }
                else if ((char1 - '0') * 10 + (char2 - '0') <= 26){
                    dp[i] += dp[i - 2];
                }
            }

            dp[i] %= 1000000007;
        }

        return (int)dp[n];
    }
}