#include<stdio.h>
#define mod 666013
int main()
{
	FILE *f, *g;
	f = fopen("kfib.in", "r");
	g = fopen("kfib.out", "w");
	int r;
	long long int k, a, b, c, d, w, x, y, z, m, n, o, p;
	fscanf(f, "%lld", &k);
	
	/*long long int sol = 1;
	fscanf(f, "%lld %lld", &n, &p);
	while(p)
	{
		r = p%2;
		if(r)
			sol *= n;
		n *= n;
		p/=2;
	}
	fprintf(g, "%lld\n", sol);*/
	a = 0; b = 1; c = 1; d = 1; w = 0; y = 1; x = 1; z = 1;
	while(k)
	{
		r = k%2;
		if(r)
		{
			m = a * w + b * y;
			n = a * x + b * z;
			o = c * w + d * y;
			p = c * x + d * z;
			a = m % mod; 
			b = n % mod;
			c = o % mod;
			d = p % mod;
		}
		m = w * w + x * y;
		n = w * x + x * z;
		o = y * w + z * y;
		p = y * x + z * z;
		w = m % mod;
		x = n % mod;
		y = o % mod;
		z = p % mod;
		k/=2;
	}
	
	fprintf(g, "%lld\n", a);
	fclose(g);
	return 0;
}