F. Kaiji!
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Itou Kaiji, a smart gambler, lost all his money once again and owed Hyodo Kazutaka a huge sum of money, who is very cruel and proposes a game to bet on Kaiji's four fingers!

Hyodo has a box with $$$n$$$ nearly identical balls in it, where the $$$i$$$-th ball has an integer number $$$a_i(1\le i \le n)$$$ on it, which is the only difference among the balls. At the first, Kaiji will be blindfolded, which means that he cannot see anything, then Hyodo will arbitrarily choose two close balls(Formally, assuming that the two chosen balls are $$$i$$$ and $$$j$$$, there is no $$$k$$$ that $$$(a_i-a_k)(a_j-a_k) \lt 0$$$), take them out of the box and put them into Kaiji's two hands. After that, Kaiji has to say "left hand" or "right hand", and Hyodo will tell him the number on the ball in the claimed hand. Finally, the most important part, Kaiji will answer the size relationship(greater than, less than, or equal to) between the told number and the number on the ball in the other hand. If Kaiji's answer is correct, he will be forgiven the debt, or he will lose his life.

Now, Kaiji needs your help, he wants to know the highest winning probability that can be guaranteed no matter what Hyodo's strategy is.

Note Kaiji will know all the numbers on balls and the whole rule before he is blindfolded.

Input

The first line contains one integer $$$T\,(1 \le T \le 1000)$$$, denoting the number of test cases.

For each test case:

Only one line contains $$$6$$$ integer $$$n\,(2 \le n \le 10^7), a_0, A, B, C\,(0 \le a_0, A, B, C \le 10^9), M\,(1 \le M \le n)$$$, denoting the number of balls and generate parameters of $$$a$$$, where $$$$$$a_i = (A \cdot a_{i - 1}^2 + B \cdot a_{i - 1} + C) \!\!\mod M + 1 \;\; (1 \le i \le n)$$$$$$

It is guaranteed that $$$ \sum{n} \le 10^7 $$$ among all test cases.

Output

For each test case:

Output one line containing one integer, denoting the winning probability modulo $$$998244353$$$.

Note that for a rational number $$$\frac{p}{q}$$$ and an integer $$$k \, (0 \le k \lt P)$$$, if $$$kq \equiv p \pmod{P}$$$ holds, we say that $$$\frac{p}{q}$$$ modulo $$$P$$$ equals $$$k$$$. In this problem, you can assume that there will be exactly one integer which equals the winning probability modulo $$$998244353$$$.

Example
Input
2
4 1 0 1 0 2
4 1 0 1 0 4
Output
499122177
665496236
Note

For the first test case:

$$$n = 4, \{a_1, a_2, a_3, a_4\} = \{2, 1, 2, 1\}$$$, one possible optimal strategy for Kaiji is:

Choose left hand or right hand randomly. Then:

  • if the heard number is 1, guess two numbers are equal with a $$$50\%$$$ probability, number on ball in the other hand is greater than number has been told with a $$$50\%$$$ probability.
  • if the heard number is 2, guess two numbers are equal with a $$$50\%$$$ probability, number on ball in the other hand is less than number has been told with a $$$50\%$$$ probability.

Under this strategy, Kaiji will have a $$$50\%$$$ probability of winning, no matter how Hyodo chooses balls.

Here $$$499122177 \times 2 \equiv 1 \pmod{998244353}$$$ and $$$499122177$$$ is the only integer which equals $$$\frac{1}{2}$$$ modulo $$$998244353$$$, so the answer integer is $$$499122177$$$.