#include <cstdio>

#define Mod (1 << 20)
#define NMAX 15000007

using namespace std;

int Dp[NMAX];
int n;

int main(){
    freopen("12perm.in", "r", stdin);
    freopen("12perm.out", "w", stdout);
    scanf("%d", &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;
    printf("%d\n", Dp[n]);
    return 0;
}