#include <stdio.h>
#define N 15000010
#define mod 1<<20
int T[N];
int main(void){
    int n,i;
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%d",&n);
    T[1] = 1, T[2] = 2, T[3] = 6, T[4] = 12;  
    for (i=5;i<=n;++i){
        T[i]=(T[i-1]+T[i-3]+2*(i-2));
        T[i]%=mod;
        //printf("%d ",i);
    }
    //for (i=1;i<=n;++i)
    printf("%d",T[n]);
    return 0;
}