#include <cstdio>
#define MOD 666013
using namespace std;
FILE *fin, *fout;
int k;
struct matrice
{
	int a[2][2];
} temp, temp1, temp3;
matrice inmultire(matrice a1, matrice b1)
{
	matrice c;
	c.a[0][0] = ((1LL*a1.a[0][0]*b1.a[0][0])%MOD + (1LL*a1.a[0][1]*b1.a[1][0])%MOD)%MOD;
	c.a[0][1] = ((1LL*a1.a[0][0]*b1.a[0][1])%MOD + (1LL*a1.a[0][1]*b1.a[1][1])%MOD)%MOD;
	c.a[1][0] = ((1LL*a1.a[1][0]*b1.a[0][0])%MOD + (1LL*a1.a[1][1]*b1.a[1][0])%MOD)%MOD;
	c.a[1][1] = ((1LL*a1.a[1][0]*b1.a[0][1])%MOD + (1LL*a1.a[1][1]*b1.a[1][1])%MOD)%MOD;
	return c;
}
matrice power(matrice a1, int b)
{
	if(b == 0) return temp1;
	if(b == 1) return a1;
	matrice temp2;
	temp2 = power(a1, b/2);
	temp2 = inmultire(temp2, temp2);
	temp2 = inmultire(temp2, power(a1, b%2));
	return temp2;
}
int main()
{
	fin = freopen("kfib.in", "r", stdin);
	fout = freopen("kfib.out", "w", stdout);
	temp.a[0][0] = 0;
	temp.a[1][0] = 1;
	temp.a[1][1] = 1;
	temp.a[0][1] = 1;
	temp1.a[0][0] = 1;
	temp1.a[1][0] = 0;
	temp1.a[1][1] = 1;
	temp1.a[0][1] = 0;
	scanf("%d", &k);
	if(k == 0) printf("0\n");
	if(k == 1) printf("1\n");
	if(k == 2) printf("1\n");
	if(k > 2)
	{
		temp3 = power(temp, k-2);
		printf("%d\n", (temp3.a[0][1] + temp3.a[1][1])%MOD);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}