program p12perm;
  const modul=1048576;
  var n,i:longint;
      a,b:array[1..5]of 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
      a[1]:=2;a[3]:=2;a[4]:=2;
      for i:=4 to n do
        begin
          b[1]:=a[1];
          b[2]:=a[4]mod modul;
          b[3]:=(a[1]+a[2]+a[3])mod modul;
          b[4]:=a[3] mod modul;
          b[5]:=(a[4]+a[5])mod modul;
          a:=b;
        end;
      writeln((a[1]+a[2]+a[3]+a[4]+a[5])mod modul);
    end;
  close(input);close(output);
end.