#include<cstdio>
#define m 666013
using namespace std;
long long z[3][3],mi[3][3],a[3][3];
int k;
void matp(int k)
{ for (;k;k>>=1)  
	{if ( k&1 ) //sol= (sol * a) % m; 
		{mi[1][1]=((a[1][1]*z[1][1])%m+ (a[1][2]*z[2][1])%m)%m;
		 mi[1][2]=((a[1][1]*z[1][2])%m+ (a[1][2]*z[2][2])%m)%m;
		 mi[2][1]=((a[2][1]*z[1][1])%m+ (a[2][2]*z[2][1])%m)%m;
		 mi[2][2]=((a[2][1]*z[1][2])%m+ (a[2][2]*z[2][2])%m)%m;
		 a[1][1]=mi[1][1]; a[2][1]=mi[2][1]; a[1][2]=mi[1][2]; a[2][2]=mi[2][2];
		}
	 mi[1][1]=((z[1][1]*z[1][1])%m + (z[1][2]*z[2][1])%m)%m;
	 mi[1][2]=((z[1][1]*z[1][2])%m + (z[1][2]*z[2][2])%m)%m;
	 mi[2][1]=((z[2][1]*z[1][1])%m + (z[2][2]*z[2][1])%m)%m;
	 mi[2][2]=((z[2][1]*z[1][2])%m + (z[2][2]*z[2][2])%m)%m;
	// a=(a * a) % m; 
	 z[1][1]=mi[1][1]; z[2][1]=mi[2][1]; z[1][2]=mi[1][2]; z[2][2]=mi[2][2];
	}
}
int main()
{freopen("kfib.in","rt",stdin);
 freopen("kfib.out","wt",stdout);
 scanf("%d",&k);
 z[1][2]=z[2][1]=z[2][2]=1;
 a[1][2]=a[2][1]=a[2][2]=1;
 matp(k-2);
 printf("%lld\n",a[2][2]);
 return 0;
}