#include <iostream>
#include <fstream>
#include <algorithm>

#define MOD 1048576

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

int n;
int a,b,c,d,i,rez;

int main()
{
    a=1;
    b=2;
    c=6;
    d=12;
    fin >> n;
    for(i=5;i<=n;i++)
    {
        rez=(d+b+2*(i-2))&MOD;
        a=b;
        b=c;
        c=d;
        d=rez;
    }
    fout << d ;
    return 0;
}