# 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;
    }
    a=6;
    b=2;
    c=1;
    for(i=4;i<=n;i++){
        aux=a+b+2*(i-2);
        c=b;
        b=a;
        if(aux>=MOD)
            aux-=MOD;
        if(aux>=MOD)
            aux-=MOD;
        a=aux;
    }
    fout<<a<<"\n";
    return 0;
}