P15733 [JAG 2024 Summer Camp #2] Expression Sum

给定一个字符串 $S$。$S$ 中的每个字符是 $\texttt{0123456789+()}$? 中的一个。 令 $T$ 为将 $S$ 中的每个 $\texttt{?}$ 替换为 $\texttt{0123456789+()}$ 中的一个字符后形成的字符串。定义 $\text{eval}(T)$ 如下： - 如果 $T$ 是一个**合法表达式**，则其值为将 $T$ 作为表达式求值得到的结果。 - 如果 $T$ 不是一个合法表达式，则其值为 $0$。 计算所有可能的替换方式（即将 $S$ 中的每个 $\texttt{?}$ 替换为 $\texttt{0123456789+()}$ 中的一个字符）所对应的 $\text{eval}(T)$ 之和，并将结果对 $998,244,353$ 取模后输出。 **合法表达式**由以下 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} $$

输入以如下格式给出： $$ S $$ - $1 \leq |S| \leq 3,000$ - $S$ 的每个字符是 $\texttt{0123456789+()}$? 中的一个。

输出答案。

翻译由 DeepSeek V3.2 完成