//#include "pch.h"
#include <iostream>
#include <fstream>

using namespace std;

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

long long k;
long long base[2][2];

static const int MOD = 666013;

void multiply(long long a[2][2], long long b[2][2])
{
	long long aux[2][2];
	
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			aux[i][j] = 0;

	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				aux[i][j] = 1LL * (aux[i][j]+(a[i][k] * b[k][j])) % MOD;

	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			a[i][j] = aux[i][j];
}

long long explog(int power)
{
	long long cur[2][2];
	cur[0][0] = cur[1][1] = 1;
	cur[0][1] = cur[1][0] = 1;

	while (power)
	{
		if (power % 2)
		{
			multiply(cur, base);
			power--;
		}
		else
		{
			multiply(base, base);
			power /= 2;
		}
	}

	return cur[1][0];
}

int main()
{
	ios::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);

	fin >> k;
	
	base[0][0] = 0;
	base[0][1] = base[1][0] = base[1][1] = 1;

	fout<<explog(k-1)<<'\n';
}