Crystal

Bajtazar works at a company that manufactures crystals. Each atom of a crystal is one of three kinds, written $A_0$, $A_1$, $A_2$. A crystal of order $n$ consists of $3n(n-1)+1$ atoms arranged into a regular hexagon with side $n-1$, which is divided into $6(n-1)^2$ equilateral triangles of side $1$. The picture below shows an example crystal of order $2$.

Crystals have an electrical property. Any three atoms that form a triangle of side $1$ and whose kinds are pairwise different produce a field of unit charge: positive if the atoms appear in the order $A_0$, $A_1$, $A_2$ when the triangle is traversed counterclockwise, or negative if that same order appears when the triangle is traversed clockwise. The charge of the whole crystal is the sum of the charges of all such triples.

Bajtazar's machine is programmed with six numbers $n$, $m$, $s$, $a$, $b$, $k$. It builds the crystal of order $n$, placing atoms row by row starting from the topmost row, and left to right within each row. The kind $A_r$ of each successive atom is chosen by running the following steps in order:

s := ((a * s + b) div k) mod (3 * m)
r := s div m

Here div is integer division (the quotient) and mod is the remainder. The two statements run one after another, once for each atom.

Compute the charge of the crystal produced for the given input parameters.

The first line contains six integers $n$, $m$, $s$, $a$, $b$, $k$ describing the machine's input parameters ($2 \le n \le 10^9$, $1 \le m \le 10^6$, $0 \le s, a, b < 3m$, $1 \le k < 3m$).

Print one integer: the charge of the crystal the machine produces.