DreamGrid 是一位著名的程序设计竞赛教练。他非常热心，许多参赛者都愿意向他请教。

DreamGrid 每天在办公室接待恰好 $n$ 位参赛者，因此会发生 $n$ 次“到达”事件和 $n$ 次“选择”事件。时间 $t$ 的到达事件表示一位参赛者在时间 $t$ 到达办公室候机室，时间 $t$ 的选择事件表示 DreamGrid 从候机室中随机（等概率）选择一位参赛者进行交谈。当然，如果选择事件发生时，候机室不能为空。交谈结束后，该参赛者离开办公室，不再回来。

几天后，DreamGrid 开始对所有合法情形下每位参赛者的总期望等待时间的平均值感到好奇。参赛者的等待时间是他被 DreamGrid 选择的时间减去他到达候机室的时间。一个情形是一个长度为 $2n$ 的序列，由 $n$ 个到达事件和 $n$ 个选择事件组成，其中第 $i$ 个事件发生在时间 $a_i$。对于一个合法的情形，必须满足当选择事件发生时，候机室不能为空。

例如，我们将到达事件记为 'A'，选择事件记为 'S'。如果 $n = 2, a_1 = 1, a_2 = 2, a_3 = 3$ 且 $a_4 = 4$，那么序列 “AASS” 是合法的，但序列 “ASSA” 是不合法的，因为在时间 $a_3 = 3$ 发生的“选择”事件是不合法的。

由于答案可能不是整数，你需要计算 $ab^{-1} \pmod p$，其中 $\frac{a}{b}$（$a$ 和 $b$ 互质）是答案，$p > 2n$ 且 $p$ 为质数，$b^{-1}$ 是 $b$ 关于模数 $p$ 的乘法逆元。容易证明 $b$ 的质因子不会大于 $2n$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含五个整数 $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$)，其中 $p$ 是一个质数。$n$ 和 $p$ 的含义如上所述。其余参数用于生成 $a$，其中 $a_0 = 0, a_i = a_{i-1} + b_i + 1$ 且 $b_i = (A \cdot b_{i-1} + B) \pmod p$，对于所有 $1 \le i \le 2n$。

保证所有测试数据中 $n$ 的总和不超过 $10^7$。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例

输入 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

1
12
1
21
879705565

说明

我们将到达事件记为 'A'，选择事件记为 'S'。

在第一组测试数据中，$a_1 = 1, a_2 = 2$，只有一种合法序列 “AS”。唯一参赛者的等待时间为 $2 - 1 = 1$，因此答案为 $1$，我们需要输出 $1 \pmod{1000000007} = 1$。

在第二组测试数据中，$a_1 = 2, a_2 = 5, a_3 = 9, a_4 = 14$。有两种合法序列 “ASAS” 和 “AASS”。

对于第一个序列，第一位到达的参赛者的期望等待时间为 $5 - 2 = 3$，第二位到达的参赛者的期望等待时间为 $14 - 9 = 5$。

对于第二个序列，第一位到达的参赛者的期望等待时间为 $((9 - 2) + (14 - 2))/2 = 9.5$，第二位到达的参赛者的期望等待时间为 $((9 - 5) + (14 - 5))/2 = 6.5$。因此答案为 $((3 + 5) + (9.5 + 6.5))/2 = 12$，我们需要输出 $12 \pmod{1000000007} = 12$。

在第三组测试数据中，$a_1 = 7, a_2 = 9, a_3 = 15, a_4 = 22$。与第二组样例的分析类似，序列 “ASAS” 的总期望等待时间为 $(9-7)+(22-15) = 9$，序列 “AASS” 的总期望等待时间为 $((15-7)+(22-7))/2+((15-9)+(22-9))/2 = 21$。因此答案为 $(9 + 21)/2 = 15$，我们需要输出 $15 \pmod 7 = 1$。