#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int n;
const int mod = 666013;

void mult_mat(int a[2][2], int b[2][2], int rez[2][2]) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			rez[i][j] = 0;
			for (int k = 0; k < 2; k++) {
				rez[i][j] = (1LL * a[i][k] * b[k][j] % mod + rez[i][j]) % mod;
			}
		}
	}
}

void copy_mat(int a[2][2], int b[2][2]) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			a[i][j] = b[i][j];
		}
	}
}

void putere()
{
	int rez[2][2] = { {1,1,},{1,0} };
	int a[2][2] = { {1, 1}, {1, 0} };
	int temp[2][2];
	int p = n - 2;
	while (p)
	{
		if (p & 1)
		{
			mult_mat(rez,a,temp);
			copy_mat(rez, temp);
		}

		mult_mat(a, a, temp);
		copy_mat(a, temp);

		p = (p >> 1);
	}

	g << rez[0][0];
}

int main()
{
	f >> n;
	if (n <= 1)
	{
		g << 1;
	}
	else {
		putere();
	}
}