题目描述

小 F 刚刚学习了如何递推。

现在她想求如下的递推数列

的第 $n$ 项的值（模素数意义下），即 $a_n\bmod p$ 。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来的 $T$ 行，每行 7 个整数 $a_0,k_1,b_1,k_2,b_2,n,p$ ($0\leq a_0<p$) ，意义如题目中所示。

输出格式

输出 $T$ 行，每行一个整数表示 $a_n\bmod p$ 。

样例

8
58 44 10 41 -44 62 73
40 77 45 62 -77 61 79
24 21 49 18 -21 37 79
51 34 7 10 -34 23 73
32 54 83 8 -54 98 89
30 4 40 52 -4 14 61
49 29 45 75 -29 47 79
8 18 7 23 -18 2 53

58
54
0
17
32
30
30
8

数据范围与约定

对于 $10\%$ 的数据， $T\leq 10,n,p\leq 100$ 。

对于 $40\%$ 的数据， $T\leq 10,n\leq 10^{18},p\leq 1000$ 。

对于 $100\%$ 的数据， $T\leq 10000,n\leq 10^{18},p\leq 10^9$ ，$p$ 是素数， $k_1,b_1,k_2,b_2\in (-p,p)$ 且不为 0 ，保证对于所有递推出的 $a_i$ ，都有 $(k_2a_i+b_2)\bmod p\neq 0$ 。