[CCPC2017秦皇岛站-B] Expected Waiting Time

内存限制：128 MB 时间限制：4000 ms

DreamGrid is a famous coach of competitive programming. He is so kind that many competitors are willing to ask him for advice.

DreamGrid meets exactly $n$ competitors every day in his office, and thus $n$ "arriving" events and $n$ "selecting" events will happen. An arriving event at time $t$ indicates that a competitor arrives at the waiting room of the office at time $t$, and a selecting event at time $t$ indicates that DreamGrid randomly selects (with equal probability) a competitor from the waiting room to talk with. Of course, if the selecting event happens, the waiting room must not be empty. After the talk, the competitor leaves the office and never comes back.

After several days, DreamGrid starts to be curious about the average of the total expected waiting time of every competitor in all valid cases. The waiting time of a competitor is the time he is selected by DreamGrid minus the time he arrives at the waiting room. A case is a sequence of length $2n$ consisting of $n$ arriving events and $n$ selecting events, where the $i$-th event will happen at time $a_i$. For a valid case, it must be satisfied that when a selecting event happens, the waiting room must not be empty.

For example, let's denote an arriving event as 'A', and a selecting event as 'S'. If $n=2$, $a_1=1$, $a_2=2$, $a_3=3$ and $a_4=4$, then the sequence "AASS" is valid, but the sequence "ASSA" is not valid, as the "selecting" event happening at time $a_3=3$ is not valid.

As the answer may not be an integer, you are supposed to calculate $ab^{-1}$ mod $p$, where $\frac{a}{b}$ ($a$ and $b$ are coprime) is the answer, $p > 2n$ and $p$ is prime, and $b^{-1}$ is the modular multiplicative inverse of $b$ with respect to the modulus $p$. It's easy to prove that the prime factors of $b$ will never be larger than $2n$.

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 10^4)$, indicating the number of test cases. For each test case:

The first line contains five integers $n$, $p$, $b_0$, $A$, $B$ $(1 \le n \le 10^6,2n < p \le 2 \times 10^9,0 \le b_0,A,B<p)$, where $p$ is a prime number. The meanings of $n$ and $p$ are described above. The rest of them is a generator of $a$, where $a_0=0$, $a_i=a_{i-1}+b_i+1$ and $b_i=(A\cdot b_{i-1}+B) \bmod p$ for all $1 \le i \le 2n$.

It is guaranteed that the sum of $n$ in all test cases does not exceed $10^7$.

For each test case, output one integer denoting the answer in a single line.

样例输入 1

5
1 1000000007 0 1 0
2 1000000007 0 1 1
2 7 5 2 3
3 31 15 6 24
20 1000000007 0 1 0

样例输出 1

C1748 [CCPC2017秦皇岛站-B] Expected Waiting Time

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示