#include<fstream>
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
int n,i,sol1,sol2,sol3,sol4;
int main(){
    fin>>n;
    if(n==1){
        fout<<"1";
        return 0;
    }
    if(n==2){
        fout<<"2";
        return 0;
    }
    if(n==3){
        fout<<"6";
        return 0;
    }
    if(n==4){
        fout<<"12";
        return 0;
    }
    sol4=2;
    sol3=6;
    sol2=12;
    for(i=5;i<=n;i++){
        sol1=(sol2+sol4+2*(i-2))%1048576;
        sol4=sol3;
        sol3=sol2;
        sol2=sol1;
    }
    fout<<sol1;
    return 0;
}