#include <stdio.h>
int n,v[15000001],i;

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