小 Vitechka 最近刚学会编程。现在他正在编写一个用于处理 $\mathbb{Z}_2$ 域上 $8 \times 8$ 矩阵的库。他将这样一个矩阵表示为一个无符号 64 位整数。从低位开始算起的第 $(8 \cdot (i - 1) + j)$ 位，存储了矩阵中第 $i$ 行第 $j$ 列交叉处的数值。例如，他将矩阵

$$ \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$

表示为数字 270。

Vitechka 编写了函数 sum(a, b) 和 multiply(a, b)，分别返回两个矩阵的和（按元素相加）和乘积。为了测试这些函数，Vitechka 使用了以下函数：

calc (n, x, p, q) {
   ans = 0;
   do n times {
      x = x * p + q;
      lhs = x;
      x = x * p + q;
      rhs = x;
      ans = sum(ans, multiply(lhs, rhs));
   }
   return ans;
}

在此伪代码中，“+” 和 “*” 是无符号 64 位整数的标准运算。

现在 Vitechka 想知道该函数在特定数据下的运行结果。

输入格式

第一行包含四个整数 $n, x, p$ 和 $q$（$1 \le n \le 10^7, 0 \le x, p, q \le 10^{18}$）。保证在除样例外的所有测试数据中，数字 $x, p$ 和 $q$ 都是均匀随机生成的。

输出格式

输出单行，包含一个整数：问题的答案。

样例

输入样例 1

1 0 1 1804

输出样例 1

5632

输入样例 2

2 111111111111111111
222222222222222222 333333333333333333

输出样例 2

12247126853369549893

说明

在第一个样例中，我们计算以下两个矩阵的乘积：

$$ \begin{pmatrix} 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \times \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} $$