const
  ha=10000;
type
  juzhen=array[1..2,1..2] of longint;
var
  c,cc:juzhen;
  i,j,k,n:longint;

function juzhen1(x,y:juzhen):juzhen;
var
  temp:juzhen;
begin
  fillchar(temp,sizeof(temp),0);
  for k:=1 to 2 do
    for i:=1 to 2 do
      for j:=1 to 2 do
      begin
        temp[i][j]:=temp[i,j] mod ha;
        x[i,k]:=x[i,k] mod ha;
        y[k,j]:=y[k,j] mod ha;
        inc(temp[i,j],(x[i,k]*y[k,j]) mod ha);
        temp[i][j]:=temp[i,j] mod ha;
      end;
  exit(temp);
end;

function pow(n:longint):juzhen;
var
  t:longint;
  temp:juzhen;
begin
  if n=1 then
    exit(cc);
  t:=n div 2;
  temp:=pow(t);
  temp:=juzhen1(temp,temp);
  if n and 1=1 then
    exit(juzhen1(temp,cc))
  else
    exit(temp);
end;

begin
  readln(n);
  while (n<>-1) do
  begin
    c[1,1]:=0;
    c[1,2]:=1;
    c[2,1]:=1;
    c[2,2]:=1;
    fillchar(cc,sizeof(cc),0);
    cc:=c;
    if (n=0) then
    begin
      writeln(0);
      //continue;
    end
    else
      if (n=1) or (n=2) then
      begin
        writeln(1);
        //continue;
      end
      else
      begin
        c:=pow(n-2);
        writeln((c[2,2]+c[1,2]) mod ha);
      end;
    readln(n);
  end;
end.