题目描述

随机数是生成随机算法的基础，小L准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数$m\ ,a\ ,\ c,\ X\_{0}$,按照下面的公式生成出一系列随机数 :

小L现在想知道这个数列第$n$个数是多少，由于他只需要生成小于$g$的随机数，所以你只需要告诉他$X_{n}\ mod\ g$的结果即可

随机数是生成随机算法的基础，小L准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数m, a, c, x0按照下面的公式生成出一系列随机数 : x(n + 1) = (a * x(n) + c) mod m 　　小L现在想知道这个数列第n个数是多少，由于他只需要生成小于g的随机数，所以你只需要告诉他x(n) mod g的结果即可

输入格式

一行6个整数，分别表示$m,\ a,\ c,\ X\_{0},\ n,\ g$
　　一行6个整数，分别表示m, a, c, x(0), n, g

输出格式

一行一个整数表示$X\_{n}$
　　一行一个整数表示x(n)

样例

####样例输入

233 3 3 3 3 333

####样例输出

120

数据范围与提示

对于$100\%$的数据:
$n\ \le\ 10^{6}$
$1\ \le \ m,\ a,\ c,\ X\_{0},\ g\ \le 2^{31}\ -\ 1$

对于100%的数据:
n <= 1e6
1 <= m, a, c, x{0}, g <= (2 << 31) - 1