#include <fstream>
#define imp 666013
using namespace std;
int main()
{
	ifstream ii("kfib.in");
	ofstream oo("kfib.out");
	unsigned long long k, i, mat[32][4], rez[4] = {1, 0, 0, 1}, rz[4], put = 1;  ii >> k;
	mat[1][0] = 0;  mat[1][1] = mat[1][2] = mat[1][3] = 1;
	for (i = 1; i < 32; i++, put *= 2)
	{
		if (i != 1)
		{
			mat[i][0] = (mat[i-1][0] * mat[i-1][0] + mat[i-1][1] * mat[i-1][2]) % imp;
			mat[i][1] = (mat[i-1][0] * mat[i-1][1] + mat[i-1][1] * mat[i-1][3]) % imp;
			mat[i][2] = (mat[i-1][0] * mat[i-1][2] + mat[i-1][2] * mat[i-1][3]) % imp;
			mat[i][3] = (mat[i-1][1] * mat[i-1][2] + mat[i-1][3] * mat[i-1][3]) % imp;
			
		}
		if (k & put)
		{
			rz[0] = mat[i][0] * rez[0] + mat[i][1] * rez[2];
			rz[1] = mat[i][0] * rez[1] + mat[i][1] * rez[3];
			rz[2] = mat[i][2] * rez[0] + mat[i][3] * rez[2];
			rz[3] = mat[i][2] * rez[1] + mat[i][3] * rez[3];
			
			rez[0] = rz[0] % imp;
			rez[1] = rz[1] % imp;
			rez[2] = rz[2] % imp;
			rez[3] = rz[3] % imp;
		}
	}
	oo << rez[2];
}