给你一个字符串 $s$。$s$ 中的每个字符都是 “0123456789+()?”（不含引号）中的一个。

设 $t$ 是将 $s$ 中的每个 ‘?’ 替换为 “0123456789+()” 中的一个字符后得到的字符串。定义 $eval(t)$ 如下：

• 如果 $t$ 是一个合法表达式，则其值为将 $t$ 作为表达式进行求值得到的结果。
• 如果 $t$ 不是一个合法表达式，则其值为 $0$。

计算对于所有可能的将 $s$ 中的每个 ‘?’ 替换为 “0123456789+()” 之一的方式，其对应的 $eval(t)$ 的总和，并将结果模 $998\,244\,353$ 后输出。

合法表达式由以下 BNF（巴科斯范式）定义：

<expression> ::= <expression> + <primary> | <primary>
<primary> ::= ( <expression> ) | <number>
<number> ::= <nonzero-digit> <number-sub> | <digit>
<number-sub> ::= <number-sub> <digit> | <digit>
<digit> ::= 0 | <nonzero-digit>
<nonzero-digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

输入格式

输入包含单行，为一个字符串 $s$（$1 \le |s| \le 3000$，$s$ 中的每个字符都是 “0123456789+()?” 之一）。

输出格式

输出一个整数，表示问题的答案。

样例

输入样例 1

?1?

输出样例 1

46306

输入样例 2

20???0+2??

输出样例 2

651059511