#include <fstream>
using namespace std;

const int mod = 666013;

long long prod[2][2];

void multiply(long long a[2][2], long long b[2][2])
{
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			prod[i][j] = (a[i][0]*b[0][j] + a[i][1]*b[1][j]) % mod;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			a[i][j] = prod[i][j];
}

int main()
{
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	int n;
	fin >> n;
	long long a[2][2] = {{1,0},{0,1}};
	long long b[2][2] = {{0,1},{1,1}};
	for (int i = 0; i < 30; ++i) {
		if (1<<i & n)
			multiply(a,b);
		multiply(b,b);
	}
	fout << a[0][1];
	return 0;
}