#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void hehe(int rez[][2], int a[2][2], int b[2][2])
{
	rez[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 666013;
	rez[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1])% 666013;
	rez[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0])% 666013;
	rez[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1])% 666013;
}

void  inm(int z[][2], int m[2][2], int k)
{
	int i = 1, w = k;
	while (w > 1)
	{
		i = i << 1;
		w = w >> 1;
	}
	int rez[2][2] = {{0,0},{0,0}};
	i  = i >> 1;
	while (i != 0)
	{
	      
		hehe(rez,z,z);	
		memcpy(z,rez,4 * sizeof(int));
		if (k & i)
		{
			hehe(rez, z, m);
			memcpy(z,rez,4 * sizeof(int));
		}
		i = i >> 1;
	}
	
}

int main()
{
	FILE * f = fopen("kfib.in", "r");
	int k;
	fscanf(f, "%i", &k);
	fclose(f);

	int z[2][2] = {{0, 1}, {1, 1}};
	int m[2][2] = {{0, 1}, {1, 1}};
	f = fopen("kfib.out", "w");
	
	if (k == 0 || k == 1)
	   ;//fprintf(f, "%i", k == 1 ? 1 : 0);
	else
	{  
	    inm(z, m, k-1);
	    fprintf(f, "%i", z[1][1]);
	}
	fclose(f);
	
	
	return 0;
}