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

#define MOD 1048575

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

inline void mul(int A[][6], int B[][6], int n, int m, int k, int C[][6])
{
	int D[6][6];
	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] = 8;
	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[2][1]=1;  M[2][2]=0; M[2][3]=0; M[2][4]=1; M[2][5]=0;
	M[3][1]=0;  M[3][2]=1; M[3][3]=0; M[3][4]=0; M[3][5]=0;
	M[4][1]=0;  M[4][2]=0; M[4][3]=1; M[4][4]=1; M[4][5]=0;
	M[5][1]=0;  M[5][2]=0; M[5][3]=0; M[5][4]=1; M[5][5]=2;
	
	for (i=0; (1<<i) <= put; ++i){
		if (put & (1<<i))
			mul(sol, M, 1, 5, 5, sol);
		mul(M, M, 5, 5, 5, M);
	}
	
	printf("%d\n", sol[1][4]);
	return 0;
}