{$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>5000010 then
 begin
  i:=5000001;
  v[2]:=994318;
  v[3]:=920600;
  int:=1030034;
 end;
if n>10000010 then
 begin
  i:=10000003;
  v[2]:=794010;
  v[3]:=464492;
  int:=750718;
 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.