#include <iostream>
#include <fstream>

const int mod = 666013;

using namespace std;

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

typedef pair <long long, long long> pii;
typedef pair<pii, pii> matrix;

//fiecare pair e cate o linie
//first 1 1
//      1 0
//el. neutru 1 0
//           0 1
matrix first = {{1, 1}, {1, 0}};
matrix neutru = {{1, 0}, {0, 1}};

int k;

matrix multiply(matrix a, matrix b){
	matrix ans;
	ans.first.first = ((a.first.first * b.first.first) + (a.first.second * b.second.first)) % mod;
	ans.first.second = ((a.first.first * b.first.second) + (a.first.second * b.second.second)) % mod;
	ans.second.first = ((a.second.first * b.first.first) + (a.second.second * b.second.first)) % mod;
	ans.second.second = ((a.second.first * b.first.second) + (a.second.second * b.second.second)) % mod;
	return ans;
}

matrix lgput(matrix n, int p){
	if(!p)
		return neutru;
	if(p == 1)
		return n;
	matrix square = multiply(n, n);
	if(p & 1)
		return multiply(n, lgput(square, p/2));
	else
		return lgput(square, p/2);
}

int main(){
	fin >> k;
	if(k)
		fout << lgput(first, k - 1).first.first;
	else
		fout << 0;
	return 0;
}