#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int n;
struct Mat
{
	int mat[2][2];
};

const Mat nullMat = {
    {{1, 0},
     {0, 1}}
};

const Mat initMat = {
    {{0, 1},
     {1, 1}}
};

Mat produs(Mat a, Mat b)
{
	Mat c;
	c.mat[0][0]=(1LL*a.mat[0][0]*b.mat[0][0]+1LL*a.mat[0][1]*b.mat[1][0])%MOD;
	c.mat[0][1]=(1LL*a.mat[0][0]*b.mat[0][1]+1LL*a.mat[0][1]*b.mat[1][1])%MOD;
	c.mat[1][0]=(1LL*a.mat[1][0]*b.mat[0][0]+1LL*a.mat[1][1]*b.mat[1][0])%MOD;
	c.mat[1][1]=(1LL*a.mat[1][0]*b.mat[0][1]+1LL*a.mat[1][1]*b.mat[1][1])%MOD;
	return c;
}

Mat exponentiere(Mat a, int n)
{
	if (n == 0) return nullMat;
	if (n % 2 == 1) return produs(a, exponentiere(produs(a, a), n/2));
	return exponentiere(produs(a, a), n/2);
}
int main()
{
	f >> n;
	g << exponentiere(initMat, n).mat[0][1] << '\n';
	return 0;
}