var p, sum:array[0..1, 1..2, 1..2] of int64;
    j, i:integer;
    k:int64;
    f, g:text;

begin
assign (f, 'kfib.in'); reset (f);
assign (g, 'kfib.out'); rewrite (g);
read (f, k);
p[1, 1, 1]:=0; p[1, 1, 2]:=1; p[1, 2, 1]:=1; p[1, 2, 2]:=1;
sum[1, 1, 1]:=1; sum[1, 1, 2]:=0; sum[1, 2, 1]:=0; sum[1, 2, 2]:=1;

i:=1; j:=1;
while k <> 0 do
  begin
  if k mod 2 = 1 then
    begin
    sum[(i+1) mod 2, 1, 1] := sum[i mod 2, 1, 1] * p[j mod 2, 1, 1]+ sum[i mod 2, 1, 2] * p[j mod 2, 2, 1];
    sum[(i+1) mod 2, 1, 1] := sum[(i+1) mod 2, 1, 1] mod 666013;
    sum[(i+1) mod 2, 1, 2] := sum[i mod 2, 1, 1] * p[j mod 2, 1, 2]+ sum[i mod 2, 1, 2] * p[j mod 2, 2, 2];
    sum[(i+1) mod 2, 1, 2] := sum[(i+1) mod 2, 1, 2] mod 666013;
    sum[(i+1) mod 2, 2, 1] := sum[i mod 2, 2, 1] * p[j mod 2, 1, 1]+ sum[i mod 2, 2, 2] * p[j mod 2, 2, 1];
    sum[(i+1) mod 2, 2, 1] := sum[(i+1) mod 2, 2, 1] mod 666013;
    sum[(i+1) mod 2, 2, 2] := sum[i mod 2, 2, 1] * p[j mod 2, 1, 2]+ sum[i mod 2, 2, 2] * p[j mod 2, 2, 2];
    sum[(i+1) mod 2, 2, 2] := sum[(i+1) mod 2, 2, 2] mod 666013;
    i:=i+1;
    end;
    p[(j+1) mod 2, 1, 1] := p[j mod 2, 1, 1] * p[j mod 2, 1, 1]+ p[j mod 2, 1, 2] * p[j mod 2, 2, 1];
    p[(j+1) mod 2, 1, 1] := p[(j+1) mod 2, 1, 1] mod 666013;
    p[(j+1) mod 2, 1, 2] := p[j mod 2, 1, 1] * p[j mod 2, 1, 2]+ p[j mod 2, 1, 2] * p[j mod 2, 2, 2];
    p[(j+1) mod 2, 1, 2] := p[(j+1) mod 2, 1, 2] mod 666013;
    p[(j+1) mod 2, 2, 1] := p[j mod 2, 2, 1] * p[j mod 2, 1, 1]+ p[j mod 2, 2, 2] * p[j mod 2, 2, 1];
    p[(j+1) mod 2, 2, 1] := p[(j+1) mod 2, 2, 1] mod 666013;
    p[(j+1) mod 2, 2, 2] := p[j mod 2, 2, 1] * p[j mod 2, 1, 2]+ p[j mod 2, 2, 2] * p[j mod 2, 2, 2];
    p[(j+1) mod 2, 2, 2] := p[(j+1) mod 2, 2, 2] mod 666013;
  j:=j+1;
  k:=k div 2;
  end;

writeln (g, sum[i mod 2, 1, 2]);
close (f); close (g);
end.