Bajtazar works at a company that manufactures crystals. Each atom of a crystal is of one of three types, conventionally denoted as $A_{0}, A_{1}, A_{2}$. A crystal of order $n$ consists of $3n(n - 1) + 1$ atoms arranged in a hexagon with side length $n-1$, composed of $6(n - 1)^{2}$ equilateral triangles with side length 1. The figure below shows an example of a crystal of order 2:

Crystals exhibit electrical properties. Every three atoms forming a triangle of side length 1 that have $pairwise\ distinct\ types$ generate an electric field with a unit charge—positive if the atoms are in the order $A_{0}, A_{1}, A_{2}$ when traversing the triangle counter-clockwise, or negative if they are in that order when traversing the triangle clockwise. The charge of the entire crystal is equal to the sum of the charges of all such triples of atoms.

Although Bajtazar has a device for producing arbitrarily large crystals, it operates in a peculiar way. The device is programmed by providing six numbers: $n$, $m$, $s$, $a$, $b$, $k$. It creates a crystal of order $n$ by placing atoms row by row, starting from the top row. Within each row, atoms are placed from left to right. The type of each successive atom $A_{r}$ is chosen pseudo-randomly by applying the following procedure:

$$ s := ((a \cdot s + b) \operatorname{div} k) \bmod (3 \cdot m) $$

$$ r := s \operatorname{div} m $$

The operation $x \operatorname{div} y$ denotes the integer part of the division of $x$ by $y$, and $x \bmod y$ is the remainder of the division of $x$ by $y$. The two instructions above are executed one after the other.

Bajtazar has asked you to write a program that determines the charge of the crystal for the given input parameters of the device.

Input

The first line of input contains six integers $n$, $m$, $s$, $a$, $b$, $k$ describing the input parameters of the crystal production device ($2 \le n \le 10^{9}$, $1 \le m \le 10^{6}$, $0 \le s, a, b < 3\cdot m$, $1 \le k < 3 \cdot m$).

Output

The only line of output should contain an integer representing the charge of the crystal produced by the device for the given parameters.

Examples

Input 1

2 7 0 5 10 1

Output 1

1