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

typedef long long fib[2][2];

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");
long long n;
fib R, t, r;

void inmultire (fib aux, fib a, fib b)
{
	aux[0][0] = (a[0][0]*b[0][0]%MD + a[0][1]*b[1][0]%MD)%MD;
	aux[0][1] = (a[0][0]*b[0][1]%MD + a[0][1]*b[1][1]%MD)%MD;
	aux[1][0] = (a[1][0]*b[0][0]%MD + a[1][1]*b[1][0]%MD)%MD;
	aux[1][1] = (a[1][0]*b[0][1]%MD + a[1][1]*b[1][1]%MD)%MD;
}

void lgput (fib rezultat, fib a, long long exp)
{
	fib aux1, aux2;
	if (exp == 1)
	{	
		aux2[0][0] = a[0][0]%MD;
		aux2[0][1] = a[0][1]%MD;
		aux2[1][0] = a[1][0]%MD;
		aux2[1][1] = a[1][1]%MD;
	}
	else if (exp%2 == 1)
	{
		lgput(aux1, a, exp - 1);
		inmultire(aux2, aux1, r);
	}
	else
	{
		lgput(aux1, a, exp/2);
		inmultire(aux2, aux1, aux1);
	}
	rezultat[0][0] = aux2[0][0]%MD;
	rezultat[0][1] = aux2[0][1]%MD;
	rezultat[1][0] = aux2[1][0]%MD;
	rezultat[1][1] = aux2[1][1]%MD;
}

int main()
{
	cin >> n;
	--n;
	r[0][0] = R[0][0] = 1;
	r[0][1] = R[0][1] = 1;
	r[1][0] = R[1][0] = 1;
	lgput(t, R, n);
	cout << t[0][0]%MD;
	return 0;
}