P15733 [JAG 2024 Summer Camp #2] Expression Sum

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{} &\ ::= \ \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 \leq |S| \leq 3,000$ - Each character of $S$ is one of $\texttt{0123456789+()}$?

Output the answer.