#include<fstream>
#include<cstring>
using namespace std;
const int MOD = 666013;
const long long I[2][2] = { 0, 1, 1, 1};

int mult(long long a[2][2], long long b[2][2], long long c[2][2]){
	int i,j,k;
	long long z[2][2];
	
	for(i=0;i<2;++i)
	  for(j=0;j<2;++j)
	  {
	  	z[i][j] = 0;
	  	for(k=0;k<2;++k)
	  	  z[i][j] = (z[i][j] + a[i][k] * b[k][j]) % MOD;
	  }
	  
	for(i=0;i<2;++i)
	  for(j=0;j<2;++j)
	    c[i][j] = z[i][j];
}

void LogPow(long long a[2][2], int P, long long ans[2][2]){
	
	ans[0][0] = ans[1][1] = 1;
	ans[1][0] = ans[0][1] = 0;
	
	for(;P;P>>=1)
	{
		if(P&1)
		{
			mult(ans,a,ans);	
		}
		mult(a,a,a);
	}
}

int main(){
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	int K;
	long long a[2][2], ans[2][2];
	
	cin>>K;
	if(K==0)
	{
		cout<<"0\n";
		return 0;
	}
	memcpy(a,I,sizeof(I));
	
	LogPow(a,K-1,ans);
	
	cout<<ans[1][1]<<'\n';
	
	return 0;
}