#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define mod 1048576

int n;
int a , b , c , d , i, rez;

int main()
{
    a = 1;
    b = 2;
    c = 6;
    d = 12;
    f >> n;
    for ( i = 5; i <= n; i++ )
    {
        rez = ( d + b + 2*(i-2) ) % mod;
        a = b;
        b = c;
        c = d;
        d = rez;
    }
    g << d ;
    return 0;
}