#include <iostream>
#include <fstream>
using namespace std;

#define mod 666013

unsigned long long *inm(unsigned long long *a, unsigned long long *b)
{
	unsigned long long i, *c = new unsigned long long[4];
	c[0] = (a[0]*b[0] + a[1]*b[2])%mod;
	c[1] = (a[0]*b[1] + a[1]*b[3])%mod;
	c[2] = (a[2]*b[0] + a[3]*b[2])%mod;
	c[3] = (a[2]*b[1] + a[3]*b[3])%mod;
	return c;
}

unsigned long long *logpow(unsigned long long *a, unsigned long long p)
{
	if (p==1) return a;
	if (p%2 == 0)
	{
		unsigned long long *c = logpow(a,p/2);
		return inm(c,c);
	}
	else
	{
		unsigned long long *c = inm(a,logpow(a,p-1));
		return c;
	}
}

int main()
{
	ifstream in("kfib.in"); ofstream out("kfib.out");
	unsigned long long *a = new unsigned long long[4];
	a[0] = 0; a[1] = 1; a[2] = 1; a[3] = 1;
	unsigned long long n; in>>n;
	a = logpow(a,n-1);
	out<<a[3];
}