#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxN 5
#define mod 1048576
using namespace std;
int n, i, j, a[maxN], x, y, z;
int main()
{
    freopen("12perm.in", "r", stdin);
    freopen("12perm.out", "w", stdout);

    scanf("%d", &n);
    a[1] = 1;
    a[2] = 2;
    a[3] = 6;
    a[0] = 12;
    for (i = 5; i <= n; ++ i)
    {
        ++ x;
        if (x == 4)
           x = 0;

        if (x - 1 < 0)
           y = 3;
        else y = x - 1;
        if (x - 3 < 0)
           z = x - 3 + 4;
        else z = x - 3;

        a[x] = (a[y] + a[z] + 2 * (i - 2) ) % mod;
    }
    printf("%d", a[x]);
    return 0;
}