#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>

using namespace std;

const int MOD = 666013;
int k;

int main() {
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	cin >> k;
	long long M[2][2] = { { 1, 1 }, { 1, 0 } };
	long long A[2][2] = { { 1, 0 }, { 0, 1 } };
	while (k) {
		if (k & 1) {
			long long T[2][2] = { { 0, 0 }, { 0, 0 } };
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					for (int k = 0; k < 2; k++) {
						T[i][j] = (T[i][j] + A[i][k] * M[k][j]) % MOD;
					}
				}
			}
			memcpy(A, T, sizeof A);
		}
		long long T[2][2] = { { 0, 0 }, { 0, 0 } };
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					T[i][j] = (T[i][j] + M[i][k] * M[k][j]) % MOD;
				}
			}
		}
		memcpy(M, T, sizeof M);
		k >>= 1;
	}
	cout << A[1][0] << endl;
	return 0;
}