#include <fstream>
using namespace std;

ifstream is("12perm.in");
ofstream os("12perm.out");

#define MOD 1048576

int N;
int A,B,C,R;

int main()
{
    is >> N;
    A = 1;
    B = 2;
    C = 6;
    R = 12;
    for ( int i = 5; i <= N; ++i )
    {
        R = C + A + 2*(i-2);
        R = R & (MOD-1);
        A = B;
        B = C;
        C = R;
    }
    os << R;
    is.close();
    os.close();
}