#include <cstdio>
#include <cstring>

using namespace std;

const int mod=666013;

class matrix
{
public:
	int a[2][2];
	matrix(){memset(a, 0, sizeof(a));}
	void operator *= (const matrix &B)
	{
		matrix C;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%mod;
		*this=C;
	}
};
matrix lgput(matrix &A, int b)
{
	matrix p;
	p.a[0][0]=p.a[1][1]=1;
	while(b)
	{
		if(b&1)p*=A;
		A*=A;
		b>>=1;
	}
	return p;
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    int k;
    scanf("%d", &k);
    matrix A;
    A.a[0][0]=A.a[0][1]=A.a[1][0]=1;
    printf("%d", lgput(A, k-1).a[0][0]);
    return 0;
}