#include <fstream>
#include <cstring>
#define NMAX 2
#define MOD 666013
#define lld long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct mat
{
	lld m[NMAX][NMAX];
	mat()
	{
		memset(m, 0, sizeof(m));
	}
};
mat mul(mat a, mat b)
{
	mat ans;
	for (int i=0;i<2;++i)
		for (int j=0;j<2;++j)
			for (int k=0;k<2;++k)
				ans.m[i][j] = ( ans.m[i][j] + a.m[i][k]*b.m[k][j] ) % MOD;
	return ans;
}
mat i2, start, ans;
mat exp(mat x, lld pw)
{
	if (!pw) return i2;
	if (pw&1) return mul(x,exp(mul(x,x),pw>>1));
	return exp(mul(x,x),pw>>1);
}
int n;
int main()
{
	fin>>n;
	if (n <= 1) return n;
	i2.m[0][0] = i2.m[1][1] = 1;
	start.m[0][0] = start.m[0][1] = start.m[1][0] = 1;
	start = exp(start, n-1);
	ans.m[0][0] = 1;
	ans = mul(start, ans);
	fout<<ans.m[0][0]<<'\n';
	fin.close();
	fout.close();
	return 0;
}