1 type 2     matrix=array[1..2,1..2]of int64; 3 var 4     a,c,p,x0,n,g:int64; 5     x,y:matrix; 6   7 function kc(x,y:int64):int64; 8 begin 9     if y=0 then exit(0);10     kc:=kc(x,y>>1);11     kc:=(kc+kc)mod p;12     if y and 1=1 then kc:=(kc+x)mod p;13 end;14  15 operator *(a,b:matrix)c:matrix;16 var17     i,j,k:longint;18 begin19     fillchar(c,sizeof(c),0);20     for i:=1 to 2 do21         for j:=1 to 2 do22             for k:=1 to 2 do23                 c[i,k]:=(c[i,k]+kc(a[i,j],b[j,k]))mod p;24 end;25  26 procedure main;27 begin28     read(p,a,c,x0,n,g);29     x[1,1]:=1;x[2,2]:=1;30     y[1,1]:=a;y[2,1]:=c;y[2,2]:=1;31     while n>0 do32         begin33             if n and 1=1 then x:=x*y;34             y:=y*y;35             n:=n>>1;36         end;37     writeln((kc(x0,x[1,1])+x[2,1])mod p mod g);38 end;39  40 begin41     main;42 end.