#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

#define MOD 666013
#define LL long long

struct M2
{
	int a11, a12, a21, a22;
};

M2 prod(M2 a, M2 b)
{
	M2 c;
	c.a11 = ((LL)a.a11 * b.a11 + (LL)a.a12 * b.a21) % MOD;
	c.a12 = ((LL)a.a11 * b.a12 + (LL)a.a12 * b.a22) % MOD;
	c.a21 = ((LL)a.a21 * b.a11 + (LL)a.a22 * b.a21) % MOD;
	c.a22 = ((LL)a.a21 * b.a12 + (LL)a.a22 * b.a22) % MOD;
	
	return c;
}

M2 power(M2 mat, int N)
{
	M2 ans;
	
	if (N == 0)
	{
		ans.a11 = 1;
		ans.a12 = 0;
		ans.a21 = 0;
		ans.a22 = 1;
		return ans;
	}	
	
	M2 half = power(mat, N/2);
	ans = prod(half, half);
	if (N % 2) ans = prod(ans, mat);
	return ans;
}

int main()
{
	freopen ("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	
	int K;
	scanf ("%d", &K);
	
	M2 G;
	G.a11 = 0;
	G.a12 = G.a21 = G.a22 = 1;
	
	M2 ans = power(G, K);
	
	printf ("%d", ans.a21);
	
	return 0;
}