#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

long long K;
long long rez;
int Z[2][2];
int r[2][2];

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

void dm()
{
	long long a,b,c,d;
	a = r[0][0];
	b = r[0][1];
	c = r[1][0];
	d = r[1][1];
	r[0][0] = (a*Z[0][0] + b*Z[1][0]) % MOD; 
	r[0][1] = (a*Z[0][1] + b*Z[1][1]) % MOD;
	r[1][0] = (c*Z[0][0] + d*Z[1][0]) % MOD;
	r[1][1] = (c*Z[0][1] + d*Z[1][1]) % MOD;
}

void put(long long P)
{
	long long a,b,c,d;
	while(P) {
		a = Z[0][0];
		b = Z[0][1];
		c = Z[1][0];
		d = Z[1][1];
		if(P % 2) {
			dm();
		}
		Z[0][0] = (a*a + b*c) % MOD;
		Z[0][1] = (a*b + b*d) % MOD;
		Z[1][0] = (c*a + d*c) % MOD;
		Z[1][1] = (c*b + d*d) % MOD;
		P /= 2;
	}
}

int main()
{
	f>>K;
	Z[1][0] = Z[0][1] = Z[1][1] = 1;
	r[0][0] = r[1][1] = 1;
	put(K-1);
	rez = r[1][1];
	g<<rez;

}