크리스털

바이트자르(Bajtazar)는 크리스털을 생산하는 회사에서 일한다. 크리스털의 각 원자는 세 종류 $A_0$, $A_1$, $A_2$ 중 하나이다. 차수(order)가 $n$인 크리스털은 $3n(n-1)+1$개의 원자로 이루어지며, 한 변의 길이가 $n-1$인 정육각형 모양으로 배열된다. 이 육각형은 한 변의 길이가 $1$인 정삼각형 $6(n-1)^2$개로 나뉜다. 아래 그림은 차수가 $2$인 크리스털의 예이다.

크리스털은 전기적 성질을 가진다. 한 변의 길이가 $1$인 정삼각형을 이루는 세 원자의 종류가 서로 모두 다르면, 이 삼각형은 크기가 $1$인 전하를 만든다. 삼각형을 반시계 방향으로 돌 때 세 원자가 $A_0$, $A_1$, $A_2$ 순서로 나타나면 전하는 양(+)이고, 같은 순서가 시계 방향으로 나타나면 음(-)이다. 크리스털 전체의 전하는 이러한 모든 삼각형이 만드는 전하의 합이다.

바이트자르의 생산 장치는 여섯 개의 정수 $n$, $m$, $s$, $a$, $b$, $k$로 프로그래밍된다. 장치는 차수가 $n$인 크리스털을 만들며, 가장 위쪽 행부터 시작하여 행 단위로 원자를 배치하고, 각 행 안에서는 왼쪽에서 오른쪽으로 배치한다. 배치되는 각 원자의 종류 $A_r$는 다음 절차를 순서대로 실행하여 정한다.

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

여기서 div는 정수 나눗셈의 몫, mod는 나머지를 뜻한다. 위 두 문장은 원자마다 한 번씩, 위에서 아래로 차례대로 실행된다.

주어진 입력 매개변수에 대해 장치가 생산하는 크리스털의 전하를 구하여라.

첫째 줄에 생산 장치의 입력 매개변수를 나타내는 여섯 개의 정수 $n$, $m$, $s$, $a$, $b$, $k$가 주어진다 ($2 \le n \le 10^9$, $1 \le m \le 10^6$, $0 \le s, a, b < 3m$, $1 \le k < 3m$).

첫째 줄에 장치가 생산하는 크리스털의 전하를 나타내는 정수 하나를 출력한다.