A message containing letters from A-Z is 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 10^9 + 7.

### Example

Example 1

```
Input: "*"
Output: 9
Explanation: You can change it to "A", "B", "C", "D", "E", "F", "G", "H", "I".
```

Example 2

```
Input: "1*"
Output: 18
```

### Notice

- The length of the input string will fit in range [1, 10^5].
- The input string will only contain the character
`*`

and digits`0`

-`9`

.

**Code (Java):**

public class Solution { /** * @param s: a message being encoded * @return: an integer */ public int numDecodings(String s) { // write your code here if (s == null || s.length() == 0) { return 0; } if (s.charAt(0) == '0') { return 0; } long MOD = (long)1e9 + 7; int n = s.length(); long[] dp = new long[n + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '*' ? 9 : 1; for (int i = 2; i <= n; i++) { char c = s.charAt(i - 1); // regular case if (c != '*') { if (c != '0') { dp[i] = dp[i - 1]; } int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1)); dp[i] += dp[i - 2] * numCombinations % MOD; } else { dp[i] = dp[i - 1] * 9 % MOD; // * match 1-9 int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1)); dp[i] += dp[i - 2] * numCombinations % MOD; } } return (int)(dp[n] % MOD); } private int getNumberOfValidNumbers(char a, char b) { // 4 cases: // * * // * num // num * // num num int ans = 0; if (a == '*' && b == '*') { ans = 15; // 11 -> 26, not 10, 20 } else if (a == '*') { int nb = Character.getNumericValue(b); if (nb >= 0 && nb <= 6) { ans = 2; // 1* and 21->26 } else { ans = 1; // 1* } } else if (b == '*') { int na = Character.getNumericValue(a); if (na == 1) { ans = 9; // 11-19 } else if (na == 2) { ans = 6; // 21-26 } else { ans = 0; } } else { int na = Character.getNumericValue(a); int nb = Character.getNumericValue(b); int num = na * 10 + nb; if (na == 0) { ans = 0; } else if (num >= 1 && num <= 26) { ans = 1; } } return ans; } }