再贴CODE
var
M,x1,x2,x0,ran,tem,d,k,t,p,q,c,e,n:int64;
i,j:longint;
procedure init;
begin
     randomize;
     readln(c,e,n);
end;

function ExGcd(a,b:int64; var x,y:int64):longint;
var r:int64;
begin
	if b = 0 then
	begin
		x:=1; y:=0;
		exit(a);
	end;
	r:=ExGcd(b,a mod b,x,y);
	tem:=x;
	x:=y;
	y:=tem-(a div b)*y;
	exit(r);
end;

function Mult(x,y:int64):int64;
var
s:int64;
begin
        s:=0;
        while y > 0 do
        begin
                if y and 1 = 1 then
                begin
                        s:=s+x;
                        if s > n then s:=s-n;
                end;
                x:=x shl 1;
                if x > n then x:=x-n;
                y:=y shr 1;
        end;
        exit(s);
end;

function Calc(x:int64):int64;
var
s,a,b:int64;
i:longint;
begin
        s:=Mult(x,x);
        s:=s+1;
        if s >= n then s:=s-n;
	exit(s);
end;

function gcd(a,b:int64):int64;
begin
	if b = 0 then exit(a);
	exit( gcd(b,a mod b) );
end;

procedure Analyse_N(n:int64);
var
i,k:longint;
quit:boolean;
begin
	if N mod 2 = 0 then
        begin
		P:=2; Q:=N div P;
		exit;
	end;
	quit:=false;
	while not quit do
	begin
		x0:=random(n-1)+1;
                x1:=Calc(x0);
                i:=1; k:=2;
		while x1 <> x0 do
                begin
                        inc(i);
                        if i = k then
                        begin
                                k:=k shl 1;
                                x0:=x1;
                        end;
                        x1:=Calc(x1);
                        if gcd(abs(x1-x0),n) > 1 then
                        begin
                                p:=gcd(abs(x1-x0),n);
                                if p <> n then
                                begin
                                        q:=n div p;
                                        exit;
                                end else break;
                        end;
		end;
	end;
end;

function Count(C,D,N:int64):int64;
var
i:longint;
sum:int64;
begin
	sum:=1;
	while D > 0 do
	begin
		if D and 1 = 1 then sum:=Mult(sum,C);
                C:=Mult(C,C);
		D:=D shr 1;
	end;
	exit(sum);
end;

procedure work;
begin
	Analyse_N(n);
	T:=(P-1)*(Q-1);
	ExGcd(E,T,D,K);
        d:=(d mod t + t) mod t;
	M:=Count(C,D,N);
	writeln(M);
end;

begin
        while not eof do
        begin
	        init;
	        work;
        end;
end.