#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>

#define ll unsigned long long 
#define MOD 666013

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

ll z[2][2] = { {0, 1}, {1, 1} };
ll m[2] = { 1, 1 };
ll k;

void inmultire_final(ll a[2], ll b[2][2]) {
	int c[2];
	c[0] = (1LL * a[0] * b[0][0] + 1LL * a[1] * b[0][1]) % MOD;
	c[1] = (1LL * a[0] * b[1][0] + 1LL * a[1] * b[1][1]) % MOD;
	a[0] = c[0], a[1] = c[1];
}

void inmultire(ll a[2][2], ll b[2][2]) {
	int c[2][2];
	c[0][0] = (1LL * a[0][0] * b[0][0] + 1LL * a[1][0] * b[0][1]) % MOD;
	c[1][0] = (1LL * a[0][0] * b[1][0] + 1LL * a[1][0] * b[1][1]) % MOD;
	c[0][1] = (1LL * a[0][1] * b[0][0] + 1LL * a[1][1] * b[0][1]) % MOD;
	c[1][1] = (1LL * a[0][1] * b[1][0] + 1LL * a[1][1] * b[1][1]) % MOD;
	a[0][0] = c[0][0], a[1][0] = c[1][0], a[0][1] = c[0][1], a[1][1] = c[1][1];
}

void exponentiere(ll Z[2][2], ll p) {
	ll r[2][2] = { {1, 0}, {0, 1} };
	while (p) {
		if (p % 2 == 1) inmultire(r, Z);
		inmultire(Z, Z);
		p /= 2;
	}
	z[0][0] = r[0][0], z[0][1] = r[0][1], z[1][0] = r[1][0], z[1][1] = r[1][1];
}

int main() {
	cin >> k;
	k--;
	exponentiere(z, k - 1);
	inmultire_final(m, z);
	cout << m[1];
}