题目描述
You are given a string S. Each character in S is one of 0123456789+()?
Let T be a string formed by replacing each ? in S with one of 0123456789+(). Define eval(T) as follows:
- If T is a valid expression, then it is the value obtained by evaluating T as an expression.
- If T is not a valid expression, then it is 0.
Compute the sum of eval(T) for all possible ways to replace each ? in S with one of 0123456789+(), and output the result modulo 998,244,353.
A valid expression is defined by the following BNF:
$$\begin{aligned}
\texttt{
} &\ ::= \ \texttt{} \ \texttt{"+"} \ \texttt{} \ | \ \texttt{} \\
\texttt{} &\ ::= \ \texttt{"("} \ \texttt{} \ \texttt{")"} \ | \ \texttt{} \\
\texttt{} &\ ::= \ \texttt{} \ \texttt{} \ | \ \texttt{} \\
\texttt{} &\ ::= \ \texttt{} \ \texttt{} \ | \ \texttt{} \\
\texttt{} &\ ::= \ \texttt{"0"} \ | \ \texttt{} \\
\texttt{} &\ ::= \ \texttt{"1"} \ | \ \texttt{"2"} \ | \ \texttt{"3"} \ | \ \texttt{"4"} \ | \ \texttt{"5"} \ | \ \texttt{"6"} \ | \ \texttt{"7"} \ | \ \texttt{"8"} \ | \ \texttt{"9"}
\end{aligned}
$$输入格式
The input is given in the following format:
S
- 1≤∣S∣≤3,000
- Each character of S is one of 0123456789+()?
输出格式
Output the answer.
?1?
46306
20???0+2??
651059511
