Description
Input
包含6个用空格分割的m,a,c,X0,n和g，其中a,c,X0是非负整数，m,n,g是正整数。
Output
输出一个数，即Xn mod g
Sample Input
11 8 7 1 5 3
Sample Output
2
快速幂+快速乘
type
matrix=array[..,..]of int64;
var
a,c,p,x0,n,g:int64;
x,y:matrix; function kc(x,y:int64):int64;
begin
if y= then exit();
kc:=kc(x,y>>);
kc:=(kc+kc)mod p;
if y and = then kc:=(kc+x)mod p;
end; operator *(a,b:matrix)c:matrix;
var
i,j,k:longint;
begin
fillchar(c,sizeof(c),);
for i:= to do
for j:= to do
for k:= to do
c[i,k]:=(c[i,k]+kc(a[i,j],b[j,k]))mod p;
end; procedure main;
begin
read(p,a,c,x0,n,g);
x[,]:=;x[,]:=;
y[,]:=a;y[,]:=c;y[,]:=;
while n> do
begin
if n and = then x:=x*y;
y:=y*y;
n:=n>>;
end;
writeln((kc(x0,x[,])+x[,])mod p mod g);
end; begin
main;
end.