#include <bits/stdc++.h>

using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
int n,a,b,c,i,nr;
int main()
{fin>>n;
if(n==1)
{
    fout<<1;
}
else if(n==2)
{
    fout<<2;
}
else if(n==3)
{
    fout<<6;
}
else if(n==4)
{
    fout<<12;
}
else{
    a=2;
    b=6;
    c=12;
    for(i=5;i<=n;i++)
    {
        nr=a+i-2+c+i-2;
        nr%= 1048576;
        b%= 1048576;
        c%= 1048576;
        a=b;
        b=c;
        c=nr;
    }
    fout<<c;
}
    return 0;
}