#include <iostream>
#include <fstream>
#define m 1048576
using namespace std;
ifstream in("12perm.in");
ofstream out("12perm.out");
int n,a,b,c,d;
int main()
{
    in>>n;
    a=12;
    b=6;
    c=2;
    d=1;
    for(int i=5;i<=n;++i)
    {
        a=b+d+2*(i-2);
        a%=m;
        d=c;
        c=b;
        b=a;
    }
    if(n==4)out<<a;
    if(n==3)out<<b;
    if(n==2)out<<c;
    if(n==1)out<<d;
    if(n>4)out<<a;
    return 0;
}