数学表达式

题目描述

小 C 有一个仅包含变量 $x$ 的数学表达式，由若干 $x,+,\times$ 以及一些合法的括号对组成（括号均由小括号表示），运算符都不能省略（不能出现 $xx, x(x+x)$ 这种形式），运算符也不能连续出现（不能有 $x+\times$）这种形式，并且不包含任何其他的常数或者符号。例如，以下是一个可能的表达式：

而这些表达式均不合法：$xx+x\times x,\; x-x,\; x(x+x),\; x+3\times x, x+\times$。

现在，小 C 把原表达式中的所有 $+,\times$ 都弄丢了，只剩下一个包含 $x$ 和括号对的字符串 $S$。例如，上述合法例子对应的 $S$ 为：xxx(xxxx)(xx)。

小 C 想要还原出原来的表达式，也就是要插入一些 $+,\times$ 到 $S$ 中，插入后得到的表达式必须满足以上规则。但这样仍然可以得到很多不同的表达式。幸运的是，小 $C$ 记得原先的表达式满足把 $x=1$ 带入后算出的值是最大的。因此，你的任务是在每个 xx，x(，)x 的中间插入 + 或者 *，使得把 $x=1$ 带入后算出的值最大，并求出这个最大值。

这个最大值可能很大，你只需要求出它对 $998244353$ 取模的结果。

请注意，本题多测。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含一个字符串 $S_i$，表示原来的表达式删去所有符号所得字符串。

输出格式

共 $T$ 行，每行一个正整数，表示答案。

样例输入

3
(xx)(x(xx)(xx)(xx(xx)x)xx)
(xx(x(xxx)x))xx
x(x(x(xx)x(xx))xx(xx)x)xx(xx)(xx)

样例输出

46
9
57

以第二个字符串为例，$(x+x+(x+(x+x+x)+x))x+x$ 在 $x=1$ 时的结果为 $9$。

数据范围

本题共包含 $20$ 个测试点。对于全部测试数据，$1\le T \le 5,1\le |S_i|\le 5000$，保证所有 $S_i$ 均合法。

| 测试点编号 | $|S_i|\le$ | 特殊性质 | | :---------: | :--------: | :---------------------: | | $1\sim 4$ | $20$ | - | | $5\sim 9$ | $100$ | - | | $10\sim 11$ | $5000$ | 所有 $S_i$ 均不包含括号 | | $12\sim 20$ | $5000$ | - |