#include <iostream>
#include <cstdio>
#define MAXN 15000050
#define MOD 1048575

using namespace std;

int rez, n;
int viz[100], sol[100];
int f[10][10] = {{1}, {1}, {1}, {2}, {1}, {3}}, a[10][10];

int good()
{
    for (int i = 1; i < n; i++)
		if (abs(sol[i]-sol[i+1]) > 2)
			return 0;
	return 1;
}

void save()
{
    if (good())
		rez++;
}

void bt(int k)
{
    if (k > n) {
		save();
		return;
    }
    for (int i = 1; i <= n; i++)
		if (!viz[i]) {
			sol[k] = i;
			viz[i] = 1;
			bt(k+1);
			viz[i] = 0;
		}
}

void mult(int x[10][10], int y[10][10]) /// product saves in x
{
	int rez[10][10];
	for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) rez[i][j] = 0;
    for (int i = 0; i < 6; i++)
		for (int j = 0; j < 6; j++)
			for (int k = 0; k < 6; k++)
				rez[i][j] = (rez[i][j] + 1LL*x[i][k]*y[k][j])&(MOD);
    for (int i = 0; i < 6; i++)
		for (int j = 0; j < 6; j++)
			x[i][j] = rez[i][j];
}

void rise(int pwr)
{
	int mat[10][10];
	for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) mat[i][j] = a[i][j], a[i][j] = 0;
    for (int i = 0; i < 6; i++) a[i][i] = 1;
    for (int i = 0; pwr>>i; i++) {
        if ((pwr>>i) & 1)
			mult(a, mat);
		mult(mat, mat);
    }
}

void solve()
{
	a[0][0] = a[0][2] = 1;
	a[1][0] = a[2][1] = 1;
	a[3][1] = a[3][2] = a[3][3] = 1;
	a[4][3] = 1;
	a[5][1] = a[5][2] = a[5][4] = a[5][5] = 1;
    rise(n-3);
    mult(a, f);
    rez = (2*a[5][0]) & MOD;
}

int main()
{
    freopen("12perm.in", "r", stdin);
	freopen("12perm.out", "w", stdout);

	scanf("%d", &n);
    //bt(1);
	solve();
	printf("%d", rez);

    return 0;
}