#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int MOD = 1048576;

int dp[5];
int N;

int add_(int a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
    return a;
}

int poz(int idx) {
    if(idx <= 0) 
        return 0;

    if(idx % 4 == 0)
        return 4;

    return idx % 4;
}

void solve() {
    cin >> N;

    dp[1] = 1, dp[2] = 2, dp[3] = 6, dp[4] = 12;
    for(int i = 5;i <= N;i++)
        dp[poz(i)] = add_(add_(dp[poz(i - 1)], dp[poz(i - 3)]), (2 * (i - 2)) % MOD);
    cout << dp[poz(N)];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("12perm");

    int T = 1;
    for(;T;T--) {
        solve();
    }

    return 0;
}