#include <stdio.h>
#include <string.h>
long long k, result[2][2]={{1,0},{0,1}}, fib, z[2][2] = { { 0, 1 }, { 1, 1 } },a,b,c,d;
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d", &k);
	while (k > 0)
	{
		if (k % 2 == 0)
		{
			a = z[0][0] * z[0][0] + z[0][1] * z[1][0];
			b = z[0][0] * z[0][1] + z[0][1] * z[1][1];
			c = z[1][0] * z[0][0] + z[1][1] * z[1][0];
			d = z[1][0] * z[0][1] + z[1][1] * z[1][1];
			z[0][0] = a  % 666013 ;
			z[0][1] = b  % 666013 ;
			z[1][0] = c  % 666013 ;
			z[1][1] = d % 666013;
			k /= 2;
		}
		else
		{
			d = result[0][0] * z[0][0] + result[0][1] * z[1][0];
			c = result[0][0] * z[0][1] + result[0][1] * z[1][1];
			b = result[1][0] * z[0][0] + result[1][1] * z[1][0];
			a = result[1][0] * z[0][1] + result[1][1] * z[1][1];
			result[0][0] = d  % 666013 ;
			result[0][1] = c  % 666013 ;
			result[1][0] = b  % 666013 ;
			result[1][1] = a  % 666013;
			k--;
		}
	}
	
	printf("%d\n", result[0][1]);
	
}