#include <cstdio>
#define MOD 1048576
using namespace std;

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