var n,i,n1,n2,n3,n4,aux:longint;
begin
assign(input,'12perm.in');reset(input);
assign(output,'12perm.out');rewrite(output);
readln(n);
if n=1 then
        begin
        write(1);
        close(output);
        exit;
        end;
if n=2 then
        begin
        write(2);
        close(output);
        exit;
        end;
if n=3 then
        begin
        write(6);
        close(output);
        exit;
        end;
if n=4 then
        begin
        write(12);
        close(output);
        exit;
        end;
n1:=12;
n2:=6;
n3:=2;
for i:=5 to n do
        begin
        aux:=n1;
        n1:=(n3+aux+2*(i-2)) mod 1048576;
        n3:=n2;
        n2:=aux;
        end;
writeln(n1);
close(input);close(output);
end.