#include <cstdio>

using namespace std;
const int p=666013;
struct mat
{
    long long a,b,c,d;
};
inline mat mult(mat A,mat B)
{
    mat AUX;
    AUX.a=(A.a*B.a%p+A.b*B.c%p)%p;
    AUX.b=(A.a*B.b%p+A.b*B.d%p)%p;
    AUX.c=(A.c*B.a%p+A.d*B.c%p)%p;
    AUX.d=(A.c*B.b%p+A.d*B.d%p)%p;
    return AUX;
}
inline mat exp(long long k,mat Z)
{
    if(k==1) return Z;
    else
        if(k%2==0)
            return mult(exp(k/2,Z),exp(k/2,Z));
        else
            return mult(mult(exp(k/2,Z),exp(k/2,Z)),Z);
}
int main()
{
    long long k;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    mat Z;
    scanf("%lld",&k);
    Z.a=0;Z.b=Z.c=Z.d=1;
    mat SOL;
    SOL=exp(k-1,Z);
    printf("%lld",SOL.d%p);
    return 0;
}