#include <fstream>

using namespace std;
ifstream f("12perm.in");
ofstream g("12perm.out");
int n,a[4],x,i;
int main()
{
    f>>n;
    a[1]=2;
    a[2]=6;
    a[3]=12;
    if(n<=4)
    {
        g<<a[n-1]<<'\n';
    }
    else
    {
        for(i=5;i<=n;i++)
        {
            x=(a[3]+a[1]+2*(i-2))%1048576;
            a[1]=a[2];
            a[2]=a[3];
            a[3]=x;
        }
        g<<a[3]<<'\n';
    }
    return 0;
}