#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

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

void fibo(int p, int a[2][2]) {

	if (p == 1) {
		a[0][0] = 1;
		a[0][1] = 1;
		a[1][0] = 1;
		a[1][1] = 0;
	}

	else
	{
		int b[2][2], c[2][2];
		if (p % 2 == 0)
		{
			fibo(p / 2, b);
			c[0][0] = b[0][0];
			c[0][1] = b[0][1];
			c[1][0] = b[1][0];
			c[1][1] = b[1][1];

		}
		else
		{
			fibo(p - 1, b);
			fibo(1, c);
		}
		a[0][0] = (1LL * b[0][0] * c[0][0] + 1LL * b[0][1] * c[1][0]) % 666013;
		a[0][1] = (1LL * b[0][0] * c[1][0] + 1LL * b[0][1] * c[1][1]) % 666013;
		a[1][0] = (1LL * b[1][0] * c[0][0] + 1LL * b[1][1] * c[1][0]) % 666013;
		a[1][1] = (1LL * b[1][0] * c[1][0] + 1LL * b[1][1] * c[1][1]) % 666013;
	}
}

int main() {
	int n, a[2][2];

	fin >> n;

	fibo(n, a);

	fout << a[0][1];

	return 0;
}