var n,i,d:longint;
    a:array[1..10] of longint;
    f,g:text;
begin
assign(f,'12perm.in'); reset(f);
readln(f,n); close(f);
a[1]:=1;
a[2]:=2;
a[3]:=6;
a[4]:=12;
d:=4;
for i:=5 to n do
begin
d:=d+1;
a[d]:=(a[d-1]+a[d-3]+2*(d-2))mod 1048576;
a[1]:=a[d-3];
a[2]:=a[d-2];
a[3]:=a[d-1];
a[4]:=a[d];
d:=d-1;
end;
assign(g,'12perm.out'); rewrite(g);
write(g,a[d]);
close(g);
end.