#include <cstdio>
#define MOD 1048576
using namespace std;

int n,a,b,c,d,e;

int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%d",&n);
    if (n == 1) printf("1\n");
    else if (n == 2) printf("2\n");
        else if (n == 3) printf("6\n");
            else if (n == 4) printf("12\n");
            else
            {
                a=1,b=2,c=6,d=12;
                for(int i = 5; i <= n; ++i)
                {
                    e = (d + b + (i-2) * 2) % MOD;
                    a=b;b=c;c=d;d=e;
                }
            }
    printf("%d\n",d);
    return 0;
}