#include<stdio.h>
#define nr 666013
using namespace std;
long long a[3][3],b[3][3],i,j,n;
long long p(long x,long y)
{
    long long m=((x*(y/100))%nr)*100+(x*(y%100))%nr;
        return m%nr;
}
void patrat()
{
    long x[3][3],i,j;
    x[1][1]=p(a[1][1],a[1][1])+p(a[2][1],a[1][2]);
    x[1][2]=p(a[1][2],(a[1][1]+a[2][2])%nr);
    x[2][1]=p(a[2][1],(a[1][1]+a[2][2])%nr);
    x[2][2]=p(a[1][2],a[2][1])+p(a[2][2],a[2][2]);
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j]%nr;
}
void echilibrare()
{
 
    if(a[1][2]<0&&a[2][1]>0)
        a[1][2]=a[2][1];
    if(a[2][1]<0&&a[1][2]>0)
    a[2][1]==a[1][2];
    if(a[1][1]<0&&a[1][2]>0&&a[2][2]>0)
    a[1][1]=a[2][2]-a[1][2];
    if(a[2][2]<0&&a[1][1]>0&&a[1][2]>0)
    a[2][2]=a[1][1]+a[1][2];
}
void produs()
{
 long x[3][3],i,j;
 
    x[1][1]=a[1][1]*b[1][1]+b[2][1]*a[1][2];
    x[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];
    x[2][1]=a[2][1]*b[1][1]+a[2][2]*b[2][1];
    x[2][2]=b[1][2]*a[2][1]+a[2][2]*b[2][2];
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j]%nr;
}
void fib(int x)
{
    if(x!=1)
    {
 
 
    fib(x/2);
    if(x%2==0)
		 patrat();
    else
    {
        patrat();
        produs();
    }
echilibrare();
    }
}
void initializare()
{
	a[2][1]=1;	b[2][1]=1;
	a[1][1]=0;
	a[1][2]=1;	b[1][2]=1;
	a[2][2]=1;	b[2][2]=1;
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);

	//for(i=1;i<=n;i++)
	{
		initializare();
	fib(n);
	printf("%lld\n",a[1][2]%nr);
	}
    return 0;
}