#include <fstream>
#define int long long

using namespace std;

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

const int MOD = 666013;
int mat[2][2] = { {0, 1}, {1, 1} };
int mat2[2][2] = { {1, 0}, {0, 1} };
int aux[2][2];

void multiply(int m1[][2], int m2[][2], int c[][2]) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			c[i][j] = 0;
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				c[i][j] += m1[i][k] * m2[k][j] % MOD;
				c[i][j] %= MOD;
			}
		}
	}
}

void copyy(int m1[][2], int m2[][2]) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			m1[i][j] = m2[i][j];
		}
	}
}

void lgput(int e) {
	int n = 1;
	while (e) {
		if (e & 1) {
			multiply(mat, mat2, aux);
			copyy(mat2, aux);
		}
		multiply(mat, mat, aux);
		copyy(mat, aux);
		e >>= 1;
	}
}

int32_t main() {
	int f1 = 1, f2 = 1;
	int n;
	cin >> n;
	lgput(n - 1);
	//cout << mat2[0][0] << ' ' << mat2[0][1] << '\n' << mat2[1][0] << ' ' << mat2[1][1] << '\n';
	cout << ((f1 * mat2[0][0]) % MOD + (f1 * mat2[1][0]) % MOD) % MOD;
	return 0;
}