#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

void mult(long long a[][2], long long b[][2]) {
	long long aux[2][2];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			aux[i][j] = 0;
			for (int k = 0; k < 2; k++) {
				aux[i][j] = (aux[i][j] + a[i][k] * b[k][j]) % mod;
			}
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			a[i][j] = aux[i][j];
		}
	}
}

int main()
{
	unsigned k;
	in >> k;
	if (k < 2) {
		out << k;
		return 0;
	}
	k -= 1;
	long long rez[2][2] = { {1,0},{0,1} };
	long long coef[2][2] = { {0,1},{1,1} };
	for (; k; k >>= 1) {
		if (k & 1) {
			mult(rez, coef);
		}
		mult(coef, coef);
	}
	out << rez[1][1];
	return 0;
}