#include <iostream>
#include <fstream>

#define modulo (1<<20)-1

using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

int n, aux, t[]={1, 2, 6, 12};

int main()
{
    fin >> n;
    if(n<=4){
        fout<<t[n-1];
        return 0;
    }
    for(int i=5; i<=n; i++){
        aux = (t[1] + t[3] + 2*(i-2))&modulo;
        t[1] = t[2];
        t[2] = t[3];
        t[3] = aux;
    }
    fout<<t[3];
    return 0;
}