#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;
#define MODULO 666013


class Matrix{
public:
	int m[2][2];

	Matrix(int numbers[][2]){
		for(int i = 0; i < 2; ++i)
			for(int j = 0; j < 2; ++j)
				m[i][j] = numbers[i][j];
	}

	Matrix operator* (Matrix B){
		int i, j, k;
		int ans[2][2];
		memset(ans, 0, sizeof(ans));

		for(int i = 0; i < 2; ++i)
			for(int j = 0; j < 2; ++j)
				for(int k = 0; k < 2; ++k)
					ans[i][j] = (1LL * m[i][k] * B.m[k][j] + ans[i][j]) % MODULO;

		Matrix answer(ans);

		return answer;
	}

	

};

int i2[2][2] = {{1, 0}, {0, 1}};
Matrix I2(i2);

int fib[2][2] = {{0, 1}, {1, 1}};
Matrix F(fib);



Matrix pow(Matrix n, long long p){
	if(p == 0)
		return I2;

	long long lsb = p % 2;
	Matrix sqr = pow(n, p/2);
	Matrix partial = (sqr * sqr);

	if(lsb == 0)
		return partial;
	else
		return (n * partial);
}

ofstream fout("kfib.out");


int main(){
	ifstream fin("kfib.in");
	int n; fin >> n;

	fout << (n != 0 ? pow(F, n).m[0][1] : 1);

}