#include <fstream>
#define MODULO 666013
using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

long long init[4][4],f[4][4],c[4][4],n;

void matmult(long long a[][4], long long b[][4], long long c[][4])
{
	c[1][1] = ((a[1][1]*b[1][1])%MODULO + a[1][2]*b[2][1])%MODULO;
	c[1][2] = ((a[1][1]*b[1][2])%MODULO + a[1][2]*b[2][2])%MODULO;
	c[2][1] = c[1][2];
	c[2][2] = ((a[1][2] * b[2][1])%MODULO + a[2][2]*b[2][2])%MODULO;
}

void matpow(long long a[][4], long long n)
{
	if(n==1)
		return;
	if(n%2)
	{
		matpow(a, n/2);
		matmult(a,a,c);
		//memcpy(a,c,sizeof(a));
		a[1][1] = c[1][1], a[1][2] = c[1][2], a[2][1] = c[2][1], a[2][2] = c[2][2];
		matmult(a,init, c);
		a[1][1] = c[1][1], a[1][2] = c[1][2], a[2][1] = c[2][1], a[2][2] = c[2][2];
		//memcpy(a,c,sizeof(a));
	}
	else
	{
		matpow(a, n/2);
		matmult(a,a,c);
		//memcpy(a,c,sizeof(a));
		a[1][1] = c[1][1], a[1][2] = c[1][2], a[2][1] = c[2][1], a[2][2] = c[2][2];
	}
}


int main()
{
	in>>n;
	if(n==1)
		{out<<1;return 0;}
	init[1][1] = init[1][2] = init[2][1] = 1;
	init[2][1] = 1;
	memcpy(f,init,sizeof(f));
	matpow(f,n-1);
	out<<f[1][1]%MODULO;
	return 0;
}