# include <fstream>
# define MOD 1048576
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
int a,b,c,aux,n,i;
int main () {
    fin>>n;
    if(n==1){
        fout<<"1\n";
        return 0;
    }
    if(n==2){
        fout<<"2\n";
        return 0;
    }
    if(n==3){
        fout<<"6\n";
        return 0;
    }
    if(n==4){
        fout<<"12\n";
        return 0;
    }
    a=12;
    b=6;
    c=2;
    for(i=5;i<=n;i++){
        aux=a+c+2*(i-2);
        c=b;
        b=a;
        if(aux>=MOD)
            aux-=MOD;
        if(aux>=MOD)
            aux-=MOD;
        if(aux>=MOD)
            aux-=MOD;
        a=aux;
    }
    fout<<a<<"\n";
    return 0;
}