#include <fstream.h>
//using namespace std;
int main(){
ifstream fin("12perm.in");
ofstream fout("12perm.out");
long N;
long b=2,c=6,d=12,Max=1048576;
fin>>N;
for (int i=5;i<=N;i++)
{
    long long aux=d;
    d=(d+b+2*(i-2));
    b=c;
    c=aux %Max;
}
if (N==4)
   fout<<12;
   else
if (N==3)
   fout<<6;
else
if (N==2)
   fout<<2;
else
if (N==1)
   fout<<1;
else
fout<<d % Max;
fout<<"\n";
fin.close();
fout.close();
return 0;
}