Problem H
Magic Sequence

One day, Bob discovers a magic sequence $\textbf{S}$ of $\textbf{N}$ integers. The sequence is generated from $3$ positive integers $A$, $B$, and $C$ as follows:

1. $S[0]$ = $A$

2. $S[i]$ = ($S[i - 1]$ * $B$ + $A$) % $C$ $(1 \leq i < N)$

Bob is really thrilled to share his invention with his crush, Alice. However, he knows that Alice does not like numbers without any specific ordering. Hence, he wants to sort the sequence before giving it to her. Please help Bob to make a progress in his relationship with Alice!

Suppose that $\textbf{R}$ is the sorted version of $\textbf{S}$. For simplicity, you don’t need to output $\textbf{R}$. Instead, you just need to output hash value of $\textbf{R}$. The hash value $\textbf{V}$ is generated using the following code:

    V = 0
    for i from 0 to N - 1:
        V = (V * X + R[i]) % Y;

Input

The first line of input contains an integer $TC$, denoting the number of test cases $(1 \le TC \le 30)$. Each test case consists of three lines:

• The first line contains one integer $N$ $(1 \le N \le 10^{6})$.

• The second line contains three integers $A$, $B$, and $C$ $(1 \le A, B, C \le 10^{9})$.

• The third line contains two integers $X$ and $Y$ $(1 \le X, Y \le 10^{9})$.

Output

For each test case, output the hash value of $\textbf{R}$.

Subtasks

1. $\textbf{(22 points)}$: $1 \le N \le 500$, $1 \le A, B, C, X, Y \le 10\, 000$

2. $\textbf{(36 points)}$: $1 \le N \le 100\, 000, 1 \le A, B, C \le 1\, 000\, 000$

3. $\textbf{(21 points)}$: $1 \le A, B, C \le 1\, 000\, 000$

4. $\textbf{(21 points)}$: No additional constraint.

3
7
7 7 12
1 20
7
16 1 15
1 14
7
2 5 6
1 19

0
1
8