#include <stdio.h>

int n;
long long v[8][8], sol[8][8];

void mul (long long a[8][8], long long b[8][8])
{
	long long c[8][8] = {0};
	int	i, j, k;
	for (i = 1; i <= 7; i ++)
		for (j = 1; j <= 7; j ++)
			for (k = 1; k <= 7; k ++)
				c[i][j] += a[i][k] * b[k][j];
	for (i = 1; i <= 7; i ++)
		for (j = 1; j <= 7; j ++)
			a[i][j] = c[i][j] & 1048575;
}

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