#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#define mod 666013
#define ff(i,n) for (i = 1; i <= n; ++i)
#define dd(i) out << i <<'\n'
using namespace std;
class matrice {
	public: int a, b, c, d;
};
matrice operator * (matrice A, matrice B) {
	matrice C;
	C.a = (1ll*A.a * B.a % mod + 1ll*A.b * B.c % mod) % mod;
	C.b = (1ll*A.a * B.b % mod + 1ll*A.b * B.d % mod) % mod;
	C.c = (1ll*A.c * B.a % mod + 1ll*A.d * B.c % mod) % mod;
	C.d = (1ll*A.c * B.b % mod + 1ll*A.d * B.d % mod) % mod;
	return C;
}
matrice putere(matrice A, int p) {
	matrice N;
	N.a = N.d = 1; N.b = N.c = 0;
	while (p > 1) {
		if(p & 1) N = N * A;
		A = A * A;
		p >>= 1;
	}
	return A*N;
}
int main(){
	/*freopen ("geamuri.in", "r", stdin);
	freopen ("geamuri.out", "w", stdout);*/
	ifstream in("kfib.in");
	ofstream out("kfib.out");
	int k;
	in >> k;
	matrice X; X.a = 0; X.b = X.c = X.d = 1;
	matrice R; R.a = R.c = R.d = 0; R.b = 1;
	X = putere(X, k);
	R = R * X;
	out << R.a;
}