#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

typedef long long lint;

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

const lint modit = 666013;

struct mat{
	int w, h;
	lint m[4][4];
};

void deb(mat ma){
	for(int y = 0; y < ma.h; ++y){
		for(int x = 0; x < ma.w; ++x){
			cout << ma.m[x][y] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}

mat id2 = {2,2,{{1,0},{0,1}}};
mat M = {2,2,{{0,1},{1,1}}};
mat W = {2,1,{{1,1}}};

mat matmult(mat &lhs, mat &rhs){
	mat r;
	r.w = rhs.w;
	r.h = lhs.h;
	for(int y = 0; y < lhs.h; ++y){
		for(int x = 0; x < rhs.w; ++x){
			r.m[x][y] = 0;
			for(int k = 0; k < lhs.w; ++k){
				r.m[x][y] += lhs.m[k][y]*rhs.m[x][k];
				r.m[x][y] %= modit;
			}
		}
	}
	return r;
}

mat matpow(mat &lhs, lint p){
	mat r = id2;
	mat kp = lhs;
	for(int i = 1; i <= p; i<<=1){
		if(p&i){
			r = matmult(r, kp);
		}
		kp = matmult(kp, kp);
	}
	return r;
}

int main(){
	// ios_base::sync_with_stdio(false);
	lint n;
	fin >> n;
	mat ans = matpow(M,n);
	ans = matmult(W, ans);
	fout << ans.m[1][0];
	return 0;
}