Problem Description

After learning the concept of differentiation in calculus, Little R’s math teacher asked him to do some derivative exercises to deepen his understanding.

However, the exceptionally smart Little R is not interested in complicated exercises. He wants you to help him design a program to compute the derivative of a given function $f(x)$.

If you are not familiar with the concept of derivatives, please refer to the content in the “Explanation”.

Input Format

The first line contains a positive integer $T$, indicating the number of exercises Little R needs to finish, i.e., the number of testdata groups.

For each testdata group, the first line is a non-empty string describing the input function $f(x)$. Let $p=998244353$.

The string may contain the following elements:

1. Monomials with coefficient $1$, including $x^1,x^2,x^0$, etc. We guarantee that the exponent is a non-negative integer (it is not omitted when it is $1$) and does not exceed $p-1$. All exponent symbols are written as ^.
2. Constants, such as $0,19260817$, etc. We guarantee that all constants are non-negative integers and do not exceed $p-1$.
3. Composite functions. The above two kinds of functions can be combined by addition, multiplication, exponentiation, parentheses, etc. In mathematics, multiplication signs and parentheses may be omitted, but we guarantee that they are never omitted in any case (and there is no meaningless redundancy, i.e., there will be no ((x)),(3)+(4)). We guarantee that any exponent is a constant, i.e., there is no case like $x^{g(x)}$.

Under the above rules, we find that after differentiating, $f(x)$ must be a polynomial function. If you are still uncertain about the input format, you can check the additional sample files.

Because outputting such a function directly is technically difficult, to verify whether your output is correct, the second line of each testdata group contains two integers in $[0,p)$. You need to output two integers: the values of the derivative function after substituting these integers, taken modulo $p$.

Note: In this problem, we treat $0^0=1$.

Output Format

Output $T$ lines. Each line contains two integers, whose meaning has been explained in the “Input Format”.

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

Hint

It is guaranteed that the string length does not exceed $10^4$, and the total length of all strings does not exceed $5 \times 10^5$.

Subtask ID	Special Properties	Score
1	$T \le 10^4$, string length does not exceed $20$, constants do not exceed $9$	20
2	$T \le 100$, the input is a simplified polynomial	15
3	$T \le 100$, constants do not exceed $9$
4	$T \le 100$, no polynomial exponentiation exists	20
5	$T \le 100$	30

We provide 5 additional sample files, each satisfying the restrictions of the 5 subtasks.

Link: https://pan.baidu.com/s/1dVSy8tU3pqGoq1-7CFYtBw Extraction code: ya2u

We only guarantee that the following definitions apply in this problem.

The derivative of $f(x)$ is a function $f'(x)$ such that:

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

We say $\displaystyle \lim_{x \to a}g(x)=L$ if and only if for any real number $\epsilon > 0$ we can find a real number $\delta > 0$ such that $\lvert g(x)-L\rvert < \epsilon$ when $0 < \lvert x - a \rvert < \delta$.

You may need the following differentiation formulas:

1. $f(x)=C,f'(x)=0$, where $C$ is a constant.
2. $f(x)=x^n,f'(x)=nx^{n-1}$, where $n$ is a non-zero constant.
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)$.

Translated by ChatGPT 5