#include <fstream>
#include <iostream>
#include <cstring>

#define MOD 1048576

using namespace std;

ifstream f("12perm.in") ;
ofstream g("12perm.out") ;

int v[10] , n ;

int main()
{
    f >> n ;
    v[1] = 1 ;
    v[2] = 2 ;
    v[3] = 6 ;
    v[0] = 12;

    for(int i = 5 ; i <= n ; ++i){
        if(i % 4 == 1){
            v[1] = (v[0] + v[2] + 2 * (i - 2)) % MOD ;
        }

        if(i % 4 == 2){
            v[2] = (v[1] + v[3] + 2 * (i - 2)) % MOD ;
        }

        if(i % 4 == 3){
            v[3] = (v[2] + v[0] + 2 * (i - 2)) % MOD ;
        }

        if(i % 4 == 0){
            v[0] = (v[3] + v[1] + 2 * (i - 2)) % MOD ;
        }
    }

    g << v[n % 4] ;
    return 0;
}