#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;

#define mod 1048576

int n ;

int v[4] = { 1, 2, 6, 12 } ;

int rezolvare(int N)
{
    if( N <= 4 )
        return v[ N - 1 ] ;

    for(int i = 5; i <= N; ++i )
    {
        int act = ( v[3] + v[1] + 2 * ( i - 2 ) ) % mod ;
        v[1] = v[2] ;
        v[2] = v[3] ;
        v[3] = act ;
    }

    return v[3] ;
}

void citire()
{
    freopen("12perm.in", "r", stdin);
    freopen("12perm.out", "w", stdout);

    cin >> n ;
}

void afisare()
{
    cout << rezolvare(n) ;
}

int main ()
{
    citire() ;

    afisare() ;

    return 0 ;
}