#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef long long ll;
const int MOD=666013;
ll n, m, i, j, k;
struct matrix
{
	ll A[2][2];
	ll *operator [](const int x)
	{
		return A[x];
	}
	matrix operator*(matrix &B)
	{
		matrix C;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				{
					C[i][j]=0;
					for(int k=0;k<2;k++)
					C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
				}
		return C;
	}
	matrix()
	{
	int i, j;
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			A[i][j]=0;
	}
};
matrix lgput(matrix A, ll p)
{
	matrix ans;
	ans[0][0]=ans[1][1]=1;
	while(p)
	{
		if(p%2)
		{
			ans=ans*A;
			p--;
		}
		else
		{
			A=A*A;
			p/=2;
		}
	}
	return ans;
}
int main()
{
	fin>>k;
	matrix fib;
	fib[0][1]=fib[1][0]=fib[1][1]=1;
	matrix ans=lgput(fib,k);
	cout<<ans[0][1]<<'\n';
}