Bajtazar 在一家从事晶体生产的企业工作。每个晶体中的原子属于三种类型之一，通常用 $A_{0}$、$A_{1}$、$A_{2}$ 表示。阶数为 $n$ 的晶体由 $3n(n - 1) + 1$ 个原子组成，这些原子排列成一个边长为 $n - 1$ 的六边形，六边形由 $6(n - 1)^{2}$ 个边长为 1 的正三角形构成。下图展示了一个阶数为 2 的晶体示意图：

晶体具有电性。每三个构成边长为 1 的三角形的原子，若它们的类型 两两不同，则会产生一个单位电荷场 —— 若沿逆时针方向围绕该三角形原子的顺序为 $A_{0}, A_{1}, A_{2}$，则电荷为正；若沿顺时针方向顺序为该排列，则电荷为负。整个晶体的电荷等于所有原子三元组电荷的总和。

虽然 Bajtazar 拥有能够制造任意大晶体的设备，但这台设备的运作方式相当特殊。它的设置需输入六个数值参数：$n$、$m$、$s$、$a$、$b$、$k$。它会生成一个阶数为 $n$ 的晶体，并按行放置原子，从最上方的行开始。每一行中的原子从左至右排列。每个新原子的类型 $A_{r}$ 是通过伪随机方式产生的，使用以下过程：

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

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

运算 $x$ div $y$ 表示 $x$ 除以 $y$ 的整数部分，$x$ mod $y$ 表示 $x$ 除以 $y$ 的余数。上述两条指令依次执行。

Bajtazar 请你编写一个程序，来根据给定的设备输入参数，计算出该晶体的电荷。

输入格式

输入的第一行包含六个整数 $n$、$m$、$s$、$a$、$b$、$k$，分别表示晶体生成设备的参数（$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$）。

输出格式

输出一行一个整数，表示使用这些参数生成的晶体的电荷。

样例

输入

2 7 0 5 10 1

输出

1