program p12perm;
  const modul=1048576;
  var n,i:longint;
      a1,a2,a3,a4,a5,b1,b2,b3,b4,b5: longint;

begin
  assign(input,'12perm.in');
  reset(input);
  assign(output,'12perm.out');
  rewrite(output);
  readln(n);
  if (n=1)or(n=2) then writeln(n) else
    begin
      a1:=2;b1:=2;a3:=2;a4:=2;
      for i:=4 to n do
        begin
          if i mod 2 =0 then
            begin
              b2:=a4;
              b3:=(a1+a2+a3)mod modul;
              b4:=a3;
              b5:=(a4+a5)mod modul;
            end else
            begin
              a2:=b4;
              a3:=(b1+b2+b3)mod modul;
              a4:=b3;
              a5:=(b4+b5)mod modul;
            end;

        end;
      if n mod 2=1 then writeln((a1+a2+a3+a4+a5)mod modul)
                   else writeln((b1+b2+b3+b4+b5)mod modul);
    end;
  close(input);close(output);
end.