#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <set>
using namespace std;
#define Max 666013

long long f[][2]={{0,1},{1,1}};;
long long r[][2]={{0,1},{1,1}};
long long x[2][2];
int n;

void pow(int n)
{
	if(n>1)
	{
		pow(n/2);
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		{
			x[i][j]=r[i][j];
			r[i][j]=0;
		}
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		for(int k=0;k<2;k++)r[i][j]=(r[i][j]+x[i][k]*x[k][j])%Max;
		if(n%2==1)
		{
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		{
			x[i][j]=r[i][j];
			r[i][j]=0;
		}
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		for(int k=0;k<2;k++)r[i][j]=(r[i][j]+x[i][k]*f[k][j])%Max;
		}
	}
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
		scanf("%d",&n);
		pow(n+1);
		printf("%lld\n",r[0][0]);
	return 0;
}