#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("12perm.in");
ofstream g ("12perm.out");
int n;
int d[1000];
int main()
{
    d[0]=2;
    d[1]=6;
    d[2]=12;
    f>>n;
    if(n<=2)
    {
        g<<n;
        return 0;
    }
    int i=5, t;
    while(i<=n)
    {
        t=(d[0]+d[2] + 2*(i-2));
        t=t%(1<<20);
        t+=1<<20 + 1<<20;
        t=t%(1<<20);
        d[0]=d[1];
        d[1]= d[2];
        d[2]=t;
        i++;
    }
    g<<d[2];
    return 0;
}