type numar=array[0..100] of longint;
const baza=1000000000;
var a,b,c:numar;
nr,i:byte;
rr,r,n:integer;
f:text;
procedure afisare(a:numar);
var f:text;
    i:integer;
    p:longint;
begin
assign(f,'nunta.out');rewrite(f);
write(f,a[n]);
for i:=a[0]-2 downto 1 do begin
    p:=baza div 10;
    while (p>a[i]) and (p>1) do begin
          write(f,0);
          p:=p div 10;
    end;
    write(f,a[i]);
end;
close(f);
end;
begin
assign(f,'nunta.in');reset(f);
readln(f,n);
close(f);
r:=0;
a[0]:=1;
a[1]:=1;
for i:=2 to n+1 do
a[i]:=(a[i-1]+a[i-2]+r) mod baza;
afisare(a);
end.