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

void afisare(long long a[][2]) {
	cout << a[0][0] << " " << a[0][1] << '\n' << a[1][0] << " " << a[1][1] << '\n';
}

void copiere(long long a[2][2], long long b[2][2]) {
	for (int i = 0; i <= 1; i++)
		for (int j = 0; j <= 1; j++)
			a[i][j] = b[i][j];
}

void inmultire(long long a[2][2], long long b[2][2], long long c[2][2]) {
	int i, j, k;
	for (i = 0; i <= 1; i++)
		for (j = 0; j <= 1; j++) {
			c[i][j] = 0;
			for (k = 0; k <= 1; k++) {
				c[i][j] += a[i][k] * b[k][j];
				c[i][j] %= MOD;
			}
		}
}

int n;

int main() {
	cin >> n;
	if (n <= 2) {
		fout << 1;
		return 0;
	}

	n -= 2;
	long long a[2][2] = { { 1,1 },{ 1,0 } };
	long long r[2][2] = { { 1,0 },{ 0,1 } };
	long long b[2][2];

	cout << "a=\n"; afisare(a); cout << "r=\n"; afisare(r);

	while (n) {
		if (n & 1) {
			inmultire(r, a, b);
			copiere(r, b);
			cout << "a intrat \n";
			cout << "a=\n"; afisare(a); cout << "r=\n"; afisare(r); cout << "b=\n"; afisare(b);
		}
		inmultire(a, a, b);
		copiere(a, b);
		cout << "a=\n"; afisare(a);
		cout << "b=\n"; afisare(b);
		n /= 2;
		cout << n << '\n';

	}
	cout << (r[0][0] + r[0][1]) % MOD;

	system("pause");
	return 0;
}