题目描述

栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。

栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 $m,a,c,x_0$，按照下面的公式生成出一系列随机数 $x_n x_{n+1} = (ax_n + c) \bmod m$，其中 $\bmod$ $m$ 表示前面的数除以 $m$ 的余数。

从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++ 和 Pascal 的产生随机数的库函数使用的也是这种方法。

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 $x_n$ 是多少。

由于栋栋需要的随机数是 $[0,g)$ 之间的，他需要将 $x_n$ 除以 $g$ 取余得到他想要的数，即 $x_n \bmod g$，你只需要告诉栋栋他想要的数 $x_n \bmod g$ 是多少就可以了。

输入格式

第一行六个整数 $m,a,c,x_0,n,g$，其中 $a,c,x_0$ 是非负整数，$m,n,g$ 是正整数。

输出格式

一行一个整数表示 $x_n\bmod g$。

11 8 7 1 5 3

2

样例解释

计算得 $x_n=x_5=8$，所以 $x_n\bmod g=8\bmod 3=2$。

数据规模与约定

对于 $100\%$​​ 的数据，$n,m,a,c,x_0 \leq 10^{18}$，$g\leq 10^8$，$n,m,g\ge 1$，$a,c,x_0\ge 0$。