Decode Ways II

Given a string s containing digits and the wildcard '*', return the number of possible decodings, where '*' can represent any digit from 1 to 9. Pattern focus: Decode ways. Wildcards greatly expand the transition count, so each state must account for both one-character and two-character interpretations.

Input Format

s = digit string with wildcard '*'

Output Format

number of valid decodings

Constraints

• 1 <= s.length <= 10^5; s contains digits and '*'

Examples

s = "*"

9

s = "1*"

18