#include <stdio.h>
#define NMAX 3
#define MOD 666013
#define ll long long
int n,A[NMAX][NMAX],B[NMAX][NMAX],rez[NMAX][NMAX],exp;
void init()
{
	A[1][2]=1;
	B[2][1]=1; B[1][2]=1; B[2][2]=1;
	rez[1][1]=1; rez[2][2]=1;
}
void mul(int A[][NMAX],int B[][NMAX])
{
	int i,j,k;
	int C[NMAX][NMAX];
	ll x;
	for (i=1; i<=2; i++)
		for (j=1; j<=2; j++)
		{
			C[i][j]=0;
			for (k=1; k<=2; k++)
			{
				x=(ll)A[i][k]*B[k][j]; 
				if (x>=MOD)
					x%=MOD;
				C[i][j]+=x;
				if (C[i][j]>=MOD)
					C[i][j]-=MOD;
			}
		}
	for (i=1; i<=2; i++)
		for (j=1; j<=2; j++)
			A[i][j]=C[i][j];
}
void lgput()
{
	while (exp)
	{
		if (exp & 1)
			mul(rez,B);
		mul(B,B);
		exp>>=1;
	}
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	exp=n;
	init();
	lgput();
	mul(A,rez);
	printf("%d\n",A[1][1]);
	return 0;
}