#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long nr=666013;
int Z[3][3]={{0,1},{1,1}}, Solutie[3][3];

void MatrixMUL(int matrA[][3], int matrB[][3], int matrRez[][3]) {
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int d = 0; d < 2; d++) 
				matrRez[i][j] = (matrRez[i][j] + matrA[i][d] * matrB[d][j]) % nr;
			
}

int fibExp(int n) {
	int cpy[3][3], aux[3][3], i;
	
	memcpy(cpy, Z, sizeof(Z));
	Solutie[0][0] =1;
    Solutie[1][1] = 1;

	while(n) {
		memset(aux, 0, sizeof(aux));
		if (n%2) {
			MatrixMUL(Solutie, cpy, aux);
			memcpy(Solutie, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		MatrixMUL(cpy, cpy, aux);
		memcpy(cpy, aux, sizeof(cpy));
        n/=2;
    }
    return Solutie[1][1];
}

int main() {
	
	int n;
    f>>n;
	g<<fibExp(n - 1);

	return 0;
}