#include <stdio.h>
#include <string.h>
#define N 2
#define MOD 666013
#define lint long long int

struct vector 
{
	vector()
	{
		memset(data,0,sizeof(data));
	}
	lint data[N];
};

struct matrix
{
	matrix()
	{
		memset(data,0,sizeof(data));
	}
	lint data[N][N];
	matrix operator* (matrix& rhs)
	{
		matrix res;
		for (int i = 0; i < N; ++i)
			for (int j = 0 ; j < N ; ++j)
				for (int k = 0 ; k < N ; ++k)
				{
					res.data[i][j] += (data[i][k] * rhs.data[k][j]) % MOD;
					res.data[i][j] %= MOD;
				}

		return res;
				
	}
	vector operator* (vector& rhs)
	{
		vector rez;
		for (int i = 0 ; i < N ; ++i)
			for (int j = 0 ; j < N ; ++j)
			{
				rez.data[i] += (rhs.data[j] * data[i][j]) % MOD;
				rez.data[i] %= MOD;
			}

		return rez;
	}
};

matrix identity()
{
	matrix res;
	for (int i = 0 ; i < N; ++i)
		res.data[i][i] = 1;
	return res;
}

matrix m;
vector v;

matrix fastexp(matrix b,int e)
{
	if ( e == 0)
		return identity();
	if ( e == 1)
		return b;

	matrix temp = fastexp(b,e/2);
	temp = temp * temp;

	if ( e % 2 == 0)
		return temp;

	return temp * b;
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	m.data[0][0] = 0;
	m.data[0][1] = 1;
	m.data[1][0] = 1;
	m.data[1][1] = 1;
	v.data[0] = 0;
	v.data[1] = 1;

	int n;
	scanf("%d",&n);

	m = fastexp(m,n);
	v = m * v;

	printf("%d\n",v.data[0]);
}