#include <iostream>
#include <fstream>
#define mod 666013

using namespace std;

const char iname[] = "kfib.in";
const char oname[] = "kfib.out";

ifstream fin(iname);
ofstream fout(oname);

long long A[3][3], B[3][3], C[3][3], i, j, k, MAT[3][3], N;
long long v[20000], x[20000], l;

void mul(long long A[3][3], long long B[3][3], long long C[3][3])
{	
	
	int i, j, k;
	
	for(i = 0; i < 2; i ++)
		for(j = 0; j < 2; j ++)
			for(k = 0; k < 2; k ++)
				C[i][j] = (C[i][j] + (long long)(A[i][k] * B[k][j])) % mod;
}

void lgput(int niv)
{
	int exp = niv;
	int k = 0;
	v[k ++] = exp;
	while(exp > 0)
	{
		if(exp % 2 == 0)
		{
			//mul(A, A, C);
			exp = exp / 2;  
			v[k ++] = exp;
			//memcpy(A, C, sizeof(C));
			//memset(C, 0, sizeof(C));
		}
		else
		{
			//mul(A, B, C);
			exp --;
			v[k ++] = exp;
			//memcpy(A, C, sizeof(C));
			//memset(C, 0, sizeof(C));
		}
	}
	for(i = k - 2; i >= 0; i --)
		x[l ++] = v[i];
	for(i = 0; i < l; i ++)
	{
		if(x[i] % 2 == 0 && x[i] != 0)
			mul(A, A, C);
		else
			if(x[i] != 0)
				mul(A, B, C);
		memcpy(A, C, sizeof(C));
		memset(C, 0, sizeof(C));
	}
			
}
int main()
{
	fin >> N;
	A[0][0] = 0, A[1][0] = 1, A[0][1] = 1, A[1][1] = 1;
	B[0][0] = 0, B[1][0] = 1, B[0][1] = 1, B[1][1] = 1;
	lgput(N);
	
	fout << A[1][0];
	return 0;
}