#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
using ll = long long;
ll n, c[3][3], sol[3][3];

/*
c =
(0 1)
(1 1)
*/

void inmulteste_sol() {
	ll aux[3][3];
	aux[1][1] = sol[1][1] * c[1][1] + sol[1][2] * c[2][1];
	aux[1][2] = sol[1][1] * c[1][2] + sol[1][2] * c[2][2];
	sol[1][1] = aux[1][1] % MOD;
	sol[1][2] = aux[1][2] % MOD;
}

void inmulteste_c() {
	ll aux[3][3];
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			aux[i][j] = 0;

	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			for (int h = 1; h <= 2; h++)
				aux[i][j] += c[i][h] * c[h][j];

	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			c[i][j] = aux[i][j] % MOD;
}

int main() {
	fin >> n;

	if (n == 0) {
		fout << 0;
		return 0;
	}

	c[1][1] = 0;
	c[1][2] = c[2][1] = c[2][2] = 1;

	sol[1][2] = 1;
	n--; /// avem deja primul element, mai trebuie n-1

	for (int p = 1; p <= n; p <<= 1) {
		if (p & n)
			inmulteste_sol();
		inmulteste_c();
	}

	fout << sol[1][2];
    return 0;
}