#include <fstream>

using namespace std;

const int NMAX = 15e6, MOD = (1 << 20);
int dp[NMAX + 2], n;

int main() {

    ifstream cin("12perm.in");
    ofstream cout("12perm.out");

    cin >> n;

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

    cout << dp[n] << "\n";

    return 0;
}