{$IFDEF NORMAL}
  {$I-,OBJECTCHECKS-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$I+,OBJECTCHECKS-,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$I-,OBJECTCHECKS-,Q-,R-,S-}
{$ENDIF RELEASE}

var i,n,vl,int,int1:longint;
    fi,fo:text;
    v:array[1..3] of longint;

    begin
assign(fi,'12perm.in'); reset(fi);
assign(fo,'12perm.out'); rewrite(fo);
readln(fi,n); close(fi);
case n of
 1 : begin writeln(fo,1); close(fo); halt; end;
 2 : begin writeln(fo,2); close(fo); halt; end;
 3 : begin writeln(fo,6); close(fo); halt; end;
 4 : begin writeln(fo,12); close(fo); halt; end;
end;
v[2]:=12; v[3]:=2; i:=5;  int:=6;
if n>3000010 then
 begin
  i:=3000003;
  v[2]:=313114;
  v[3]:=521452;
  int:=780286;
 end;
if n>5000010 then
 begin
  i:=5000001;
  v[2]:=994318;
  v[3]:=920600;
  int:=1030034;
 end;
if n>7000010 then
 begin
  i:=7000003;
  v[2]:=223362;
  v[3]:=625538;
  int:=205186;
 end;
if n>8000010 then
 begin
  i:=8000003;
  v[2]:=780544;
  v[3]:=18760;
  int:=760664;
 end;
if n>10000010 then
 begin
  i:=10000003;
  v[2]:=794010;
  v[3]:=464492;
  int:=750718;
 end;
if n>11000010 then
 begin
  i:=11000003;
  v[2]:=264090;
  v[3]:=719636;
  int:=192604;
 end;
if n>12000010 then
 begin
  i:=12000003;
  v[2]:=947254;
  v[3]:=43662;
  int:=93732;
 end;
if n>13000010 then
 begin
  i:=13000003;
  v[2]:=58652;
  v[3]:=579222;
  int:=719772;
 end;
if n>14000010 then
 begin
  i:=14000003;
  v[2]:=807170;
  v[3]:=759554;
  int:=705282;
 end;
while i<=n do
 begin
  v[1] := v[2] + v[3] + 2 * (i-2);
  v[1] := v[1] mod 1048576;
  int1 := v[2];
  v[2] := v[1];
  v[3] := int;
  int := int1;
  inc(i);
 end;
writeln(fo,v[1]);
close(fo);
end.