#include <iostream>
#include <cstdio>

using namespace std;

#define MAX 666013

long long K;
long long result[2][2] = {{1, 0}, {0, 1}};
long long tmp[2][2] = {{0, 1}, {1, 1}};

void multiply(long long mat1[2][2], long long mat2[2][2]){
	long long tmp[2][2];
	tmp[0][0] = ((mat1[0][0] * mat2[0][0]) % MAX + (mat1[0][1] * mat2[1][0]) % MAX) % MAX;
	tmp[0][1] = ((mat1[0][0] * mat2[0][1]) % MAX + (mat1[0][1] * mat2[1][1]) % MAX) % MAX;
	tmp[1][0] = ((mat1[1][0] * mat2[0][0]) % MAX + (mat1[1][1] * mat2[1][0]) % MAX) % MAX;
	tmp[1][1] = ((mat1[1][0] * mat2[0][1]) % MAX + (mat1[1][1] * mat2[1][1]) % MAX) % MAX;
	
	mat1[0][0] = tmp[0][0];
	mat1[0][1] = tmp[0][1];
	mat1[1][0] = tmp[1][0];
	mat1[1][1] = tmp[1][1];
	
	//cout << mat1[0][0] << " " << mat1[0][1] << " " << mat1[1][0] << " " << mat1[1][1] << endl;
}

int main(){
	freopen("kfib.in",  "rt", stdin);
	freopen("kfib.out", "wt", stdout);
	cin >> K;
	int P = K - 1;
	
	for(int i = 0; i < 32; ++i){
		if(P & (1 << i)){
			multiply( result, tmp);
		}
		multiply(tmp, tmp);
	}
	
	cout << result[1][1];
	
	return 0;
}