Description
Like Decode Ways but the message may contain "*" representing any digit 1-9. Return the total number of ways to decode, modulo 10^9 + 7.
Examples
Input:
s = "*"Output:
9Explanation:
* can be decoded as any letter A-I.
Input:
s = "2*"Output:
15Explanation:
The string "2*" can be decoded as two separate digits or as a two-digit number. In total, there are 15 ways.
Input:
s = "**"Output:
96Explanation:
The string "**" can be decoded as two separate single digits or as a two-digit number. In total, there are 96 ways.
Constraints
- •
1 ≤ s.length ≤ 10⁵ - •
s contains digits and '*'