#include <cstdio>

const char IN [ ] = "12perm.in" ;
const char OUT [ ] = "12perm.out" ;
const int MAX = 15000014 ;
const int MOD = 1048576 ;

using namespace std;

/*
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
*/

int v [ MAX ] ;

int gen ( int n )
{
    v [ 1 ] = 1 ;
    v [ 2 ] = 2 ;
    v [ 3 ] = 6 ;
    v [ 4 ] = 12 ;
    for ( int i = 5 ; i <= n ; ++ i )
        v [ i ] = ( v [ i - 1 ] + v [ i - 3 ] + ( ( i - 2 ) << 1 ) ) % MOD ;
    return v [ n ] ;
}
int main(   )
{
    int n ;
    freopen( IN , "r" , stdin ) ;
    freopen( OUT , "w" , stdout ) ;
    scanf( "%d", &n ) ;
    printf ( "%d\n" , gen ( n ) ) ;
    return 0;
}