#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

int k;
int sol[2][2];
int mat[2][2];


void mult (int A[][2], int B[][2], int C[][2])
{
	int i, j, k;
	for (int i = 0; i <=1; i++)
	{
		for (int j = 0; j <= 1; j++)
		{
			for (int k = 0; k <= 1; k++)
			{
				C[i][j] = (C[i][j]+ 1LL * A[i][k] * B[k][j])%666013;
			}
		}
	}
}

void lg_power(int p)
{
	int aux[2][2];
	sol[0][0] = 1;
	sol[1][1] = 1;//matricea unitate
	 for (int i = 0; (1<<i) <= p; ++i)
	 {
	 	if ((1<<i) & p)
	 	{
	 		memset(aux,0, sizeof(aux));
	 		mult(sol, mat, aux);
	 		memcpy(sol, aux, sizeof(aux));
	 	}
	 	memset(aux,0, sizeof(aux));
	 	mult (mat, mat, aux);
	 	memcpy(mat, aux, sizeof(aux));
	 }
}

int main()
{
	freopen("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	cin>>k;
	mat[0][0] = 0;
	mat[0][1] = 1;
	mat[1][0] = 1;
	mat[1][1] = 1;
	lg_power(k-1);
	printf ("%d", sol[1][1]);
}