说明

给定一个 $n$个点 $m$条边的无向连通图，编号为 $1$到 $n$，没有自环，可能有重边，每一条边有一个正权值 $w$。

给出 $q$个询问，每次给出两个不同的点 $u$和 $v$，求一条从 $u$到 $v$的路径上边权的最大值最小是多少。

输入格式

输入第一行两个整数 $n, m$。

接下来 $m$行，每行三个整数 $a_i, b_i, w_i(a_i$ ≠ $b_i)$，表示一条边 $(a_i, b_i)$，边权为 $w_i$。

接下来一行一个整数 $q$，表示询问数量。

接下来一行四个整数 $A, B, C, P$，表示询问的生成方式。

由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输入压缩方法是：读入 $4$ 个整数 $A, B, C, P$，每次询问调用以下函数生成 $u$和 $v$：

int A, B, C, P;
inline int rnd(){ return A = (A * B + C) % P; }

每次询问时的调用方法为：

u = rnd() % n + 1, v = rnd() % n + 1;

若 $u$ 和 $v$ 相等则答案为 $0$。

数据保证 $0 \le A < P$，$0 \le C < P$，$P(B+1) < 2^{31} - 1$。

输出格式

输出共一行一个整数，表示所有询问的答案之和模 $1000000007$的值。

由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输出压缩方法是：输出所有询问的答案之和模 $1000000007$的值。

样例

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817

32

提示

对于所有数据，$n \le 70000$，$m \le 100000$，$q \le 10^7$。