#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define modul 1048576


int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);

    int one = 2, two = 6, three = 12, n, i, temp;

    scanf("%d", &n);

    if(n == 1)
    {
        printf("1\n");
        return 0;
    }
    if(n == 2)
    {
            printf("2\n");
            return 0;
    }
    if(n == 3)
    {
        printf("6\n");
        return 0;
    }
    if(n == 4)
    {
        printf("12\n");
        return 0;
    }

    for(i = 5; i <= n; ++i)
    {
        temp = (one + three + 2 * (i - 2)) % modul;
        one = two;
        two = three;
        three = temp;
    }

    printf("%d\n", three);


    return 0;
}