#include <cstdio>
#define MOD 666013
using namespace std;


class Matrix
{
private:
    long long a,b,c,d;
public:
    Matrix()
    {
        a=1;
        b=0;
        c=0;
        d=1;
    }
    Matrix(int x,int y,int z,int t)
    {
        a=x;
        b=y;
        c=z;
        d=t;
    }

    long long take(Matrix &m,int y)
    {
        if(y==1)
            return a;
        if(y==2)
            return b;
        if(y==3)
            return c;
        if(y==4)
            return d;
        return -1;
    }

    Matrix &operator=(Matrix m)
    {
        a=m.a;
        b=m.b;
        c=m.c;
        d=m.d;
        return *this;
    }
    Matrix operator*(Matrix m)
    {
    Matrix t=*this;
    a=(t.a*m.a)%MOD + (t.b*m.c)%MOD;
    a=a%MOD;
    b=(t.a*m.b)%MOD + (t.b*m.d)%MOD;
    b=b%MOD;
    c=(t.c*m.a)%MOD + (t.d*m.c)%MOD;
    c=c%MOD;
    d=(t.c*m.b)%MOD + (t.d*m.d)%MOD;
    d=d%MOD;
    return *this;
    }
    Matrix operator%(long long k)
    {
        a=a%k;
        b=b%k;
        c=c%k;
        d=d%k;
        return *this;
    }
    Matrix operator^(long long n)
    {
        long long p=n;
        Matrix t=Matrix(1,0,0,1);
        Matrix l=*this;
        while(n>1)
        {
        if(n%2==1)
            {
            t=(t*l);
            t=t % MOD;
            n--;
            }
        l=(l*l);
        l=l % MOD;
        n/=2;
        }
        Matrix f=l*t;
        f=f% MOD;
        return f;
    }


};

long long citire()
{
unsigned long long k;
scanf("%lld",&k);
return k;
}


long long NrFib(long long k)
{
    Matrix b(1,1,1,0);
    b=b^(k-1);
    return b.take(b,1);
}

void Afis(long long k)
{
    printf("%lld",k);
}



int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long k;
    k=citire();
    k=NrFib(k);
    Afis(k);

    return 0;
}