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 in two ways: 1) As two separate digits: '2' (B) and '*' (any of A-I), giving 1×9=9 ways. 2) As a two-digit number: '2*' can form 21-26 (U-Z), giving 6 ways. Total: 9+6=15 ways.
Input:
s = "**"Output:
96Explanation:
The string "**" can be decoded as: 1) Two separate single digits: first '*' has 9 choices (1-9), second '*' has 9 choices (1-9), giving 9×9=81 ways. 2) One two-digit number: '**' can represent 11-19 (9 ways) and 21-26 (6 ways), giving 15 ways. Total: 81+15=96 ways.
Constraints
- •
1 ≤ s.length ≤ 10⁵ - •
s contains digits and '*'