#include <fstream>
#define mod 1048576

using namespace std;

 ifstream x ("12perm.in");
 ofstream y ("12perm.out");

 int n;

int main()
{
    x>>n;
    if(n==1)
       y<<1<<'\n';
    if(n==2)
       y<<2<<'\n';
    if(n==3)
       y<<6<<'\n';
    if(n==4)
       y<<12<<'\n';

    if(n>4)
    {
        int a,b,c,d,i;
        a=2;
        b=6;
        c=12;

        for(i=5;i<=n;i++)
        {
            d=(c+a+2*(i-2))%mod;
            a=b;
            b=c;
            c=d;
        }
        y<<d<<'\n';
    }

    return 0;
}