#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;
class matrix
{
	public:
	long long val[2][2];
	matrix()
	{
		memset(val,0,sizeof val);
	}
	void operator*=(matrix m)
	{
		matrix r;
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)
			{
				for(int k=0;k<2;++k)
					r.val[i][j]+=val[i][k]*m.val[k][j];
				r.val[i][j]%=MOD;
			}
		*this=r;
	}
};
matrix pow(matrix m,int p)
{
	matrix sol;
	sol.val[0][0]=sol.val[1][1]=1;
	while(p)
	{
		if(p&1)
			sol*=m;
		m*=m;
		p>>=1;
	}
	return sol;
}
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int main()
{
	matrix c;
	c.val[0][1]=c.val[1][0]=c.val[1][1]=1;
	int k;
	fin>>k;
	c=pow(c,k-1);
	fout<<c.val[1][1]<<"\n";
	return 0;
}