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
          if i mod 2 =0 then
            begin
              b[2]:=a[4];
              b[3]:=(a[1]+a[2]+a[3])mod modul;
              b[4]:=a[3];
              b[5]:=(a[4]+a[5])mod modul;
            end else
            begin
              a[2]:=b[4];
              a[3]:=(b[1]+b[2]+b[3])mod modul;
              a[4]:=b[3];
              a[5]:=(b[4]+b[5])mod modul;
            end;

        end;
      if n mod 2=1 then writeln((a[1]+a[2]+a[3]+a[4]+a[5])mod modul)
                   else writeln((b[1]+b[2]+b[3]+b[4]+b[5])mod modul);
    end;
  close(input);close(output);
end.