#include <fstream>

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 ] + 1LL * 2 * ( i - 2 ) ) % MOD ;
    return v [ n ] ;
}
int main(   )
{
    int n ;
    fin >> n ;
    fout << gen ( n ) << '\n' ;
    return 0;
}