#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

using namespace std;
// using namespace __gnu_pbds;
// template<typename T>
// using oset = tree<T, null_type, less<T>,
				  // rb_tree_tag, tree_order_statistics_node_update>;

#define nl cout.put('\n')
using ll = long long;
using ull = unsigned long long;

#ifdef Wi_TEST
	template<typename T1, typename T2>
	ostream& operator<<(ostream& out, pair<T1,T2> p) {
		out << "(" << p.first << ", " << p.second << ")";
		out.flush(); return out;
	}
	void DEB() { cerr << "]" << endl; }
	template<typename H, typename ... T>
	void DEB(H h, T... t) {
		cerr << h;
		if(sizeof...(t)) cerr << ", ";
		DEB(t...);
	}
	#define deb(...) cerr << "LINE(" << __LINE__ << ") -> [" << \
						     #__VA_ARGS__ << "]: [", DEB(__VA_ARGS__)
#else
	#define deb(...) 87105
#endif

const long long MOD = 666013, MOD2 = 998244353;
int lx[] = {0, 1, 0, -1}, ly[] = {1, 0, -1, 0};

#define N 100005

void mult(ll A[2][2], ll B[2][2]) {
	ll C[2][2];
	C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
	C[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
	C[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1];
	C[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1];
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			A[i][j] = C[i][j] % MOD;
}

void mat_pow(ll A[2][2], int p) {
	if (p == 0) {
		A[0][0] = A[1][1] = 1;
		A[1][0] = A[0][1] = 0;
	} else if ((p & 1) == 0) {
		mult(A, A);
		mat_pow(A, p / 2);
	} else {
		ll B[2][2];
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				B[i][j] = A[i][j];
		mult(A, A);
		mat_pow(A, p / 2);
		mult(A, B);
	}
}

void solve() {
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	
	int n;
	fin >> n;
	if (n <= 1)
		fout << n;
	else {
		ll A[2][2] = {{1, 1}, {1, 0}};
		mat_pow(A, n - 1);
		fout << A[0][0];
	}
}

int main() {
	ios_base::sync_with_stdio(false);
#ifndef Wi_TEST
	cin.tie(0);
#endif
	
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; ++i) {
		solve();
	}
}