#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
#define MOD 666013
int pattern[2][2];
int fibo[2][2];
void inmultire(int a[2][2], int b[2][2])
{
	int newFibo[2][2] = {};
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				newFibo[i][j] = (newFibo[i][j] + 1LL*a[i][k] * b[k][j]) % MOD;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			a[i][j] = newFibo[i][j];
}
void kfib(int n)
{
	if (n <= 1)
	{
		cout << 1;
		return;
	}
	pattern[0][0] = 0;
	pattern[0][1] = 1;
	pattern[1][0] = 1;
	pattern[1][1] = 1;
	fibo[0][0] = 0;
	fibo[0][1] = 1;
	fibo[1][0] = 1;
	fibo[1][1] = 1;
	n -= 2;
	while (n)
	{
		if (n % 2)
			inmultire(fibo, pattern);
		n /= 2;
		inmultire(pattern, pattern);
	}
	cout << fibo[1][1];
}
int main()
{
	int n;
	cin >> n;
	kfib(n);
}