#include<stdio.h>
const long long d=666013;
long long a[2][2]={{0,1},{1,1}}, f0=0,f1=1,k;

void trans( long long b[2][2], long long a[2][2])
{
    long long x1=b[0][0],y1=b[0][1],z1=b[1][0],t1=b[1][1],x2=a[0][0],y2=a[0][1],z2=a[1][0],t2=a[1][1];
    b[0][0]=(x1*x2+y1*z2)%d;
    b[0][1]=(x1*y2+y1*t2)%d;
    b[1][0]=(z1*x2+t1*z2)%d;
    b[1][1]=(z1*y2+t1*t2)%d;

}
long long kfib( long long p)
{

    long long b[2][2]={{1,0},{0,1}};
    while(p)
    {
        if(p%2)
            trans(b, a);
        trans(a,a);
        p/=2;
    }
	return b[1][0]%d;
}



void citire()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld", &k);

}

int main()
{
    citire();
    printf("%lld",kfib(k));
    return 0;
}