#include <cstdio>
using namespace std;
const int MOD = 1048576;
int v[5];

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