#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 15000002
#define mod 1048576
using namespace std;
int n, i, j, a[Nmax];
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[4] = 12;
    for (i = 5; i <= n; ++ i)
        a[i] = (a[i - 1] + a[i - 3] + 2 * (i - 2) ) % mod;
    printf("%d", a[n]);
    return 0;
}