#include <bits/stdc++.h>

using namespace std;

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

long long a[2][2];
long long z[2][2];
long long ans[2][2];
int n;
const int MOD=666013;
void multiply(long long a[2][2],long long b[2][2])
{
	long long ans[2][2];
	memset(ans,0,sizeof(ans));
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
		{
			for(int k=0;k<=1;k++)
				ans[i][j]+=a[i][k]*b[k][j];
			ans[i][j]%=MOD;
		}
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
			a[i][j]=ans[i][j];
}

void lgput(long long sol[2][2],int power)
{
	while(power)
	{
		if(power%2)
		{
			multiply(sol,z);
			power--;
		}
		else
		{
			multiply(z,z);
			power/=2;
		}
	}
}


int main()
{
	a[0][1]=1;
	z[0][0]=0;
	z[0][1]=1;
	z[1][0]=1;
	z[1][1]=1;
	ans[1][0]=1;
	ans[1][1]=1;
	in>>n;
	lgput(ans,n-1);
	multiply(a,ans);
	out<<a[0][0]<<"\n";
	return 0;
}