#include <stdio.h>

FILE *F = fopen("12perm.in", "r");
FILE *G = fopen("12perm.out", "w");

int n, perm[4] = {1, 2, 6, 12};

int main()
{
    fscanf(F, "%d", &n);
    fclose(F);
    if (n <= 4)
        fprintf(G, "%d", perm[3]);
    else
    {
        for (int i = 5; i <= n; i++)
        {
            perm[0] = perm[1];
            perm[1] = perm[2];
            perm[2] = perm[3];
            perm[3] = (perm[0] + perm[2] + 2 * i - 4) & 1048575;
        }
        fprintf(G, "%d", perm[3]);
    }
    fclose(G);
    return 0;
}