{$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>1000010 then
 begin
  i:=1000003;
  v[2]:=440192;
  v[3]:=244168;
  int:=793816;
 end;
if n>2000010 then
 begin
  i:=2000003;
  v[2]:=67648;
  v[3]:=95990;
  int:=67810;
 end;
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>6000010 then
 begin
  i:=6000003;
  v[2]:=926108;
  v[3]:=931606;
  int:=109596;
 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>9000010 then
 begin
  i:=9000003;
  v[2]:=766144;
  v[3]:=246646;
  int:=283746;
 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.