#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;

struct matrice{ 
	int n, m;
	vector <vector <int>> x;
	
	matrice(int _n, int _m) : n(_n), m(_m), x(n, vector <int> (m)) {}; 

	matrice operator *(const matrice &rhs) {
		matrice res(n, rhs.m);
		if (m != rhs.n) assert(1 == 0);
		for (int i = 0; i < n ; ++i) for (int j = 0; j < m ; ++j) for (int k = 0; k < rhs.m ; ++k) 
			res.x[i][k] = (res.x[i][k] + 1LL * x[i][j] * rhs.x[j][k]) % MOD;

		return res;
	}

	template <typename T>
	void init(int i, int j, T v) {x[i][j] = v;}

	template <typename T, typename... Args>
	void init(int i, int j, T v, Args... args) {
		if (j == m) j = 0, ++i;	
		x[i][j] = v;
		init(i, j + 1, args...);
	}

	void afis() {
		for (auto lin : x) {
			for (auto elem : lin) 
				cerr << elem << " ";	
			cerr << endl;
		}
	}
};

matrice lgput(const matrice &A, int p) {
	matrice aux = A, ans(2, 2);
	ans.init(0, 0, 1, 0, 0, 1);

	for (int i = 1; i <= p ; i = i << 1) {
		if (i & p) ans = ans * aux;
		aux = aux * aux;
	}

	return ans;
}

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	int n;
	scanf("%d", &n);

	matrice A(2, 2);
	A.init(0, 0, 0, 1, 1, 1);
	A = lgput(A, n - 1);
	//A.afis();

	printf("%d", A.x[1][1]);
	
	return 0;
}