#include<fstream>
#define mod 666013

using namespace std;

struct matrice{
	long long a;
	long long b;
	long long c;
	long long d;
};
int k;
matrice inmultire(matrice A,matrice B)
{
	matrice aux;
	aux.a = (((A.a%mod)*(B.a%mod))%mod + ((A.b%mod)*(B.c%mod))%mod)%mod;
	aux.b = (((A.a%mod)*(B.b%mod))%mod + ((A.b%mod)*(B.d%mod))%mod)%mod;
	aux.c = (((A.c%mod)*(B.a%mod))%mod + ((A.d%mod)*(B.c%mod))%mod)%mod;
	aux.d = (((A.c%mod)*(B.b%mod))%mod + ((A.d%mod)*(B.d%mod))%mod)%mod;
return aux;
}
matrice power(matrice A, int p)
{
	if(p == 1)return A;
	else if(p%2 != 0) return inmultire(A,power(A,p-1));
	else{
			matrice q = power(A,p/2);
			return inmultire(q,q);
	}
}
int main()
{
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	
	matrice Zk,Z;
	fin>>k;
	if(k == 0)
		{
			fout<<0<<"\n";
			return 0;
	    }
	else if(k == 1)
	{
		fout<<1<<"\n";
		return 0;
	}
	Z.a = 0;Z.b = Z.c = Z.d = 1;
	Zk = power(Z,k-1);
fout<<Zk.d<<"\n";

fin.close();
fout.close();

return 0;
}