#include<stdio.h>
#include<string.h>
#define ll long long
#define mod 666013
using namespace std;

int n;
ll A[3][3],B[3][3];
void inm(ll a[3][3],ll b[3][3])
{
	ll c[3][3];
	
	memset(c,0,sizeof(c));
	
	c[0][0]=((ll)a[0][0]*b[0][0] + (ll) a[0][1]*b[1][0] ) %mod;
	c[0][1]=((ll)a[0][0]*b[0][1] + (ll) a[0][1]*b[1][1] ) %mod;
	
	c[1][0]=((ll)a[1][0]*b[0][0] + (ll) a[1][1]*b[1][0] ) %mod;
	c[1][1]=((ll)a[1][0]*b[0][1] + (ll) a[1][1]*b[1][1] ) %mod;

memcpy(B,c,sizeof(c));	
}

void putere(int k)
{
	if(k==0||k==1)	return;
	
	else if(k%2==0)
	{
		putere(k/2);
			inm(B,B);		
	}
	else {
		putere(k/2);
		inm(B,B);
		inm(B,A);	
	}
}

int main()
{
	FILE *f=fopen("kfib.in","r"), *g=fopen("kfib.out","w");

fscanf(f,"%d",&n);

A[0][0]=B[0][0]=0; A[0][1]=B[0][1]=1;
A[1][0]=B[1][0]=1; A[1][1]=B[1][1]=1;

putere(n);

fprintf(g,"%lld",B[0][1]);

return 0;
}