//#include <iostream>
#include <fstream>
#include <vector>

#define MOD 666013

using namespace std;


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


void matmul(long long int M1[3][3], long long int M2[3][3]) {
	long long int M[3][3];
	M[0][0] = (M1[0][0]*M2[0][0]+M1[0][1]*M2[1][0]) % MOD;
	M[0][1] = (M1[0][0]*M2[0][1]+M1[0][1]*M2[1][1]) % MOD;
	M[1][0] = (M1[1][0]*M2[0][0]+M1[1][1]*M2[1][0]) % MOD;
	M[1][1] = (M1[1][0]*M2[0][1]+M1[1][1]*M2[1][1]) % MOD;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			M1[i][j] = M[i][j];
		}
	}
}

void ridicare_log_mod_matrix(long long int M[3][3], int power) {
	long long S2[3][3];
	S2[0][0] = 0;
	S2[0][1] = 1;
	S2[1][0] = 1;
	S2[1][1] = 1;
	while (power) {
		if (power & 1) {
			matmul(M, S2);
			power--;
		}
		else {
			matmul(S2, S2);
			power /= 2;
		}
	}
}

int main(){// al k-lea numar din sirul lui Fibonacci
	int k;
	cin >> k;
	long long int M[3][3];
	if (k == 1)
		cout << 1;
	if (k == 2)
		cout << 1;
	else {
		long long S[3][3];
		S[0][0] = 1;
		S[0][1] = 0;
		S[1][0] = 0;
		S[1][1] = 1;
		ridicare_log_mod_matrix(S, k);
		cout << S[0][1]% MOD;
	}
    return 0;
}