//implementation of miller test without big numbers (maximum range is range of longint)
//author: Michal Pilipczuk
//XIV Secondary High School, Warsaw, Poland

program miller;
uses bignumber;
var hand_in:text;
i,dl,b,k,t,p:longint;
w1,w2:qword;
wej:string;
flag,flag2:boolean;
reprezent:array[0..100] of longint;

procedure wyp(a:longint);
begin
    dl:=1;
    b:=a;
    while (1=1) do
    begin
	reprezent[dl]:=(b mod 2);
	b:=(b shr 1);
	if b=0 then break;
	dl:=dl+1;
    end;
end;

function millero(podst:longint):boolean;
begin
    w1:=1;
    flag2:=true;
    for k:=dl downto 1 do
    begin
	w2:=((w1*w1) mod i);
	if ((not((w1=1) or (w1=i-1)))and(w2=1)) then
	begin
	    flag2:=false;
	    break;
	end;
	if reprezent[k]=1 then w1:=((w2*podst) mod i) else w1:=w2;
    end;
    millero:=((flag2) and (w1=1));
end;

begin
    randomize;
    assign(hand_in,'/home/k03_a/michaj/.homepage/miller.in');
    reset(hand_in);
    readln(hand_in,wej);
    close(hand_in);
    if not(sprawdz(wej)) then
    writeln('WRONG INPUT')
    else
    begin
	i:=longintuj(wej,10);
	wyp(i-1);
	for t:=1 to 20 do
	begin
	    p:=random(i-1)+1;
	    flag:=millero(p);
	    if not(flag) then break;
	end;
	writeln(flag);
    end;
end.