#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD = 666013;

int K;
int a_static[4][4], aux[4][4], a_rez[4][4];

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

void init() {
	fin >> K;
	a_static[1][1] = 0;
	a_static[1][2] = 1;
	a_static[2][1] = 1;
	a_static[2][2] = 1;

	a_rez[1][1] = 1;
	a_rez[1][2] = 0; 
	a_rez[2][1] = 0; 
	a_rez[2][2] = 1;
};

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

	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			a[i][j] = c[i][j];
}

vector <int> binary(int num) {
	vector <int> v;
	int r;
	while (num) {
		r = num % 2;
		num /= 2;
		v.push_back(r);
	};

	reverse(v.begin(), v.end());
	return v;
}

void rezolvare_problema(vector <int> v) {
    if(v[0] == 0) { 
        v.pop_back(); 
        copiere(a_rez, a_static);
    }

	for(int i = 0; i < v.size(); i++) {
		if (v[i] == 1) {
            inmultire_matrici(a_rez, a_rez);
			inmultire_matrici(a_rez, a_static);
		} else { 
            inmultire_matrici(a_rez, a_rez);
        }
	}

	fout << a_rez[2][1] % MOD;
}

int main() {
	init(); 
	vector <int> bin; 
	bin = binary(K);
	rezolvare_problema(bin); 
	return 0; 
}