program kfib;
type
tabel=array [1..2,1..2] of int64;
var
t:tabel;
f1,f2:text;
n:longint;
procedure a1;
begin
t[1,2]:=t[1,2]*(t[1,1]+t[2,2]) mod 666013;
t[1,1]:=(sqr(t[1,1])+sqr(t[2,1])) mod 666013;
t[2,2]:=(sqr(t[2,2])+sqr(t[2,1])) mod 666013;
t[2,1]:=t[1,2];
end;
procedure a2;
begin
t[1,1]:=t[2,1];
t[2,1]:=t[2,2];
t[2,2]:=(t[1,1]+t[2,1]) mod 666013;
t[1,2]:=t[2,1];
end;
procedure putere(x:longint);
begin
if x>1 then begin
putere(x div 2);
a1;
if odd(x) then a2;
end;
end;
begin
assign (f1,'kfib.in');
assign (f2,'kfib.out');
reset (f1);
rewrite (f2);
readln (f1,n);
t[2,1]:=1; t[2,2]:=1; t[1,2]:=1;
putere(n+1);
writeln(f2,t[1,1]);
close (f1);
close (f2);
end.