题目描述

You are given a string $S$. Each character in $S$ is one of $\texttt{0123456789+()}$?

Let $T$ be a string formed by replacing each $\texttt{?}$ in $S$ with one of $\texttt{0123456789+()}$. Define $\text{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 $\text{eval}(T)$ for all possible ways to replace each $\texttt{?}$ in $S$ with one of $\texttt{0123456789+()}$, and output the result modulo $998,244,353$.

A valid expression is defined by the following BNF:

$$\begin{aligned} \texttt{<expression>} &\ ::= \ \texttt{<expression>} \ \texttt{"+"} \ \texttt{<primary>} \ | \ \texttt{<primary>} \\ \texttt{<primary>} &\ ::= \ \texttt{"("} \ \texttt{<expression>} \ \texttt{")"} \ | \ \texttt{<number>} \\ \texttt{<number>} &\ ::= \ \texttt{<nonzero-digit>} \ \texttt{<number-sub>} \ | \ \texttt{<digit>} \\ \texttt{<number-sub>} &\ ::= \ \texttt{<number-sub>} \ \texttt{<digit>} \ | \ \texttt{<digit>} \\ \texttt{<digit>} &\ ::= \ \texttt{"0"} \ | \ \texttt{<nonzero-digit>} \\ \texttt{<nonzero-digit>} &\ ::= \ \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 \leq |S| \leq 3,000$
• Each character of $S$ is one of $\texttt{0123456789+()}$?

输出格式

Output the answer.

?1?

46306

20???0+2??

651059511