给你6个数，m, a, c, x0, n, g

Xn+1 = ( aXn + c ) mod m，求Xn

m, a, c, x0, n, g<=10^18

一行六个数 m, a, c, x0, n, g

输出一个数 Xn mod g

11 8 7 1 5 3

2

int64按位相乘可以不要用高精度。

题解

由题目中 Xn+1 = (a * Xn + c) % m 可得以下矩阵：
┏ a, 0 ┓
[Xn, c] * ┃        ┃ = [Xn+1, c]
┗ 1, 1 ┛

于是做矩阵快速幂即可。

注意到m, a, c, x0, n, g <= 1018，其中a，c，X0 是非负整数，m，n，g 是正整数，所以我们对于取模运算进行一个修改，将乘法修改为倍增乘法(类似于快速幂)：

long long Multiply (long long x, long long y)
{
long long ans = 0;
while(y)
{
if(y & 1) ans = (ans + x) % m;
x = (x << 1) % m;
y >>= 1;
}
return ans;
}