#include <stdio.h>
#include <string.h>

#define MOD 1048575

int M[7][7], aux[7][7], sol[7][7];
int N, i, put;

inline void mul(int A[][7], int B[][7], int n, int m, int k, int C[][7])
{
	int D[7][7];
	memset(D, 0, sizeof(D));
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=k; ++j)
			for (int t=1; t<=m; ++t){
				long long aux = 1LL*A[i][t] * B[t][j];
				aux &= MOD;
				D[i][j] = (D[i][j] + aux) & MOD;
			}
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=k; ++j)
			C[i][j] = D[i][j];
}

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