Given an undirected graph with $n$ vertices and $m$ edges. For a subset $A$ of $\{1, 2, \dots, n\}$, the score of $A$ is defined as: 1. The initial score is 0; 2. For all $i \in A$, add $a_i$ to the score; 3. For all edges $(u, v, k)$ (representing an edge between $u$ and $v$ with value $k$) such that $u \in A$ and $v \in A$, subtract $k$ from the score.

Please calculate the maximum possible score among all subsets $A$.

Input

Read data from standard input. Let $q = 101, b = 137, p = 1,000,000,007$. The first line contains six integers $n, m, x_0, y_0, a_0, z_0$ ($1 \le n \le 100000, 0 \le m \le \frac{n}{2}, 0 \le x_0, y_0, a_0, z_0 < p$).

For $1 \le i \le n$, $a_i = (q \times a_{i-1} + b) \pmod p$. For $1 \le i \le m$, $x_i = (q \times x_{i-1} + b) \pmod p$, $y_i = (q \times y_{i-1} + b) \pmod p$, $z_i = (q \times z_{i-1} + b) \pmod p$. Each triplet $(x_i, y_i, z_i)$ describes an edge connecting $(x_i \pmod n) + 1$ and $(y_i \pmod n) + 1$ with value $z_i$. If $x_i = y_i$ or an edge connecting $x_i$ and $y_i$ has appeared before, ignore this edge (i.e., the edge does not exist).

Output

Output to standard output. Output a single integer representing the maximum score.

Examples

Input 1

1 10 5 1 2 3 4

Output 1

3909327860