题目描述

小 R 学会微积分中求导这一概念后，他的数学老师要求他开始做一部分导数的练习题加深自己的理解。

但颖悟绝伦的小 R 对繁复的练习题并不感兴趣。他希望你帮他设计一个程序，计算一个给定函数 $f(x)$ 的导数。

如果你对导数这一概念并不熟悉，请参阅【说明】中的内容。

输入格式

第一行一个正整数 $T$，表示小 R 要完成的练习题数量，亦即测试数据的组数。

每组测试数据的第一行是一个非空字符串，描述了输入的函数 $f(x)$。设 $p=998244353$。

字符串中可能包含的元素有：

1. 系数为 $1$ 的单项式，包括 $x^1,x^2,x^0$ 等，我们保证指数为非负整数（为 $1$ 时不省略）且不超过 $p-1$。所有幂号用 ^ 代替。
2. 常数，如 $0,19260817$ 等；我们保证一切常数是非负整数且不超过 $p-1$。
3. 复合函数。将以上两种函数组合的方式可以为加乘幂，括号等。数学中会省略乘号和括号，但我们保证任意情况下都不省略（也不会无意义冗余，即不存在 ((x)),(3)+(4)）；保证任何指数都是常数，即不存在 $x^{g(x)}$ 的情况。

经过以上规定，我们发现 $f(x)$ 求导后一定是一个多项式函数。如果你对数据的输入形式仍有不确定，可以观察附加样例文件。

由于输出这样的函数存在技术困难，为确认你的输出是正确的，测试数据的第二行为两个整数，值在 $[0,p)$ 之间。你需要输出两个整数，表示这些整数代入导函数后的值模 $p$ 的结果。

注意：本题中认为 $0^0=1$。

输出格式

输出 $T$ 行，每行两个整数，已在【输入格式】中说明它们的意义。

4
x
0 1
9
0 1
x*(x^(1*8))
0 1
(3*(x^3))+((2*(x^2))+(12*x))
0 1

1 1
0 0
0 9
12 25

提示

规定字符串长度不超过 $10^4$，字符串总长不超过 $5 \times 10^5$。

子任务编号	特殊性质	分值
1	$T \le 10^4$，字符串长度不超过 $20$，出现的常数不超过 $9$	20
2	$T \le 100$，输入是一个化简后的多项式	15
3	$T \le 100$，出现的常数不超过 $9$
4	$T \le 100$，不存在多项式求幂	20
5	$T \le 100$	30

我们提供了 5 个附加样例文件，分别满足 5 个子任务的限制。

链接: https://pan.baidu.com/s/1dVSy8tU3pqGoq1-7CFYtBw 提取码: ya2u

我们只保证以下定义在本题中适用。

$f(x)$ 的导数是一个函数 $f'(x)$，满足：

$$\displaystyle \lim_{h \to 0} f'(x)=\dfrac{f(x+h)-f(x)}{h} $$

我们称 $\displaystyle \lim_{x \to a}g(x)=L$ 当且仅当对于任何实数 $\epsilon > 0$ 我们都可以找到一个实数 $\delta > 0$ 使得 $\lvert g(x)-L\rvert < \epsilon$ 若 $0 < \lvert x - a \rvert < \delta$。

你可能用到以下的求导公式：

1. $f(x)=C,f'(x)=0$，其中 $C$ 是一常数。
2. $f(x)=x^n,f'(x)=nx^{n-1}$，其中 $n$ 为非 $0$ 常数。
3. $(f(x)+g(x))'=f'(x)+g'(x)$
4. $(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$
5. $(f(g(x)))'=f'(g(x))g'(x)$