You are given a string . Each character in is one of ?
Let be a string formed by replacing each in with one of . Define as follows:
- If is a valid expression, then it is the value obtained by evaluating as an expression.
- If is not a valid expression, then it is .
Compute the sum of for all possible ways to replace each in with one of , and output the result modulo .
A valid expression is defined by the following BNF:
