//implementation of miller test for prime numbers using big numbers
//efficient enough to test big numbers (for 10-digits prime it's below 2 seconds)
//author: Michal Pilipczuk
//XIV Secondary High School, Warsaw, Poland

program millerbig;
uses bignumber;
var hand_in:text;
l,t:longint;
p,iw,i,iod,w1,w2:string;
flag,flag2:boolean;

function millero(podst:string):boolean;
begin
    w1:='1';
    flag2:=true;
    for l:=1 to length(iod) do
    begin
	w2:=modulo(mul(w1,w1),i);
	if ((not((w1='1')or(w1=iod))) and (w2='1')) then
	begin
	    flag2:=false;
	    break;
	end;
	if iod[l]='1' then w1:=modulo(mul(w2,podst),i) else w1:=w2;
    end;
    millero:=((flag2)and(w1='1'));
end;

begin
    initialize;
    assign(hand_in,'/home/k03_a/michaj/.homepage/millerbig.in');
    reset(hand_in);
    readln(hand_in,iw);
    close(hand_in);
    if not(sprawdz(iw)) then
    writeln('WRONG INPUT')
    else
    begin
	i:=zmienw2(iw,10);
	iod:=od(i,'1');
	for t:=1 to 20 do
	begin
	    p:=rand(iod);
	    flag:=millero(p);
	    if not(flag) then break;
	end;
	writeln(flag);
    end;
end.