#include <iostream>
#include <fstream>

using namespace std;

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

#define NMax 5
#define MOD 666013

struct matrice{
	int n, m;
	int a[NMax][NMax];
	matrice();
};

matrice::matrice(){
	int i, j;
	for(i = 0; i < NMax; i++)
		for(j = 0; j < NMax; j++)
			a[i][j] = 0;
	n = m = 0;
}

matrice operator*(const matrice & a, const matrice & b){
	matrice sol;
	sol.n = a.n;
	sol.m = b.m;
	int i, j, k;
	for(i = 0; i < a.n; i++)
		for(j = 0; j < b.m; j++)
			for(k = 0; k < a.m; k++){
				sol.a[i][j] += (1LL * a.a[i][k] * b.a[k][j]) % MOD;
				sol.a[i][j] %= MOD;
			}
	return sol;
}

matrice a, a0;
int n;

matrice pow_log(matrice x, int p){
	if(p == 0) return a0;
	if(p % 2 == 1) return x * pow_log(x, p - 1);
	matrice nr = pow_log(x, p / 2);
	return nr * nr;
}

int main(){
	a.n = a.m = 2;
	a.a[0][0] = 0;
	a.a[1][0] = 1;
	a.a[0][1] = 1;
	a.a[1][1] = 1;
	
	a0.n = a0.m = 2;
	a0.a[0][0] = 1;
	a0.a[1][0] = 0;
	a0.a[0][1] = 0;
	a0.a[1][1] = 1;
	
	matrice b;
	fin >> n;
	b = pow_log(a, n);
	fout << b.a[0][1];
}