#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

const long long MOD = 666013;

class matrix {
private:
	long long n, m;
public:
	vector<vector<long long> >a;

	matrix()
	{
		m = n = 0;
	}

	matrix(long long x, long long y)
	{
		m = x;
		n = y;
		for (long long i = 0; i < x; i++)
		{
			vector<long long>v(y);
			a.push_back(v);
		}
	}

	matrix operator*(const matrix& other)
	{
		matrix v(m, other.n);
		for (long long i = 0; i < m; i++)
			for (long long j = 0; j < n; j++)
				for(long long k = 0; k < other.n; k++)
					v.a[i][k] = (v.a[i][k] + a[i][j] * other.a[j][k]) % MOD;
		return v;
	}

	matrix operator=(const matrix& other)
	{
		a.clear();
		m = other.m;
		n = other.n;
		for (long long i = 0; i < m; i++)
		{
			vector<long long>v(n);
			a.push_back(v);
		}
		for (long long i = 0; i < other.m; i++)
		{
			for (long long j = 0; j < other.n; j++)
				a[i][j] = other.a[i][j];
		}
		return *this;
	}

	void print()
	{
		for (long long i = 0; i < m; i++)
		{
			for (long long j = 0; j < n; j++)
				cout << a[i][j] << " ";
			cout << "\n";
		}
		cout << "\n";
	}

};

matrix lgput(matrix n, long long p)
{
	matrix a;
	matrix sol(2,2);
	sol.a[0][0] = 1;
	sol.a[1][0] = 0;
	sol.a[0][1] = 0;
	sol.a[1][1] = 1;
	a = n;
	for (long long i = 0; (1 << i) <= p; i++)
	{
		if (p & (1 << i))
			sol = sol * a;
		a = a * a;
	}
	return sol;
}

int main()
{
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");


	matrix fibo(1, 2);
	matrix b(2, 2);
	fibo.a[0][0] = 0;
	fibo.a[0][1] = 1;
	b.a[0][0] = 0;
	b.a[0][1] = 1;
	b.a[1][0] = 1;
	b.a[1][1] = 1;

	long long p;
	cin >> p;

	cout << (fibo * lgput(b, p-1)).a[0][1];

	return 0;
}