#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const long long MOD=666013;

struct Matrix
{
    long long a,b,c,d;
};

Matrix multiply(Matrix x,Matrix y)
{
    Matrix r;

    r.a=(x.a*y.a+x.b*y.c)%MOD;
    r.b=(x.a*y.b+x.b*y.d)%MOD;
    r.c=(x.c*y.a+x.d*y.c)%MOD;
    r.d=(x.c*y.b+x.d*y.d)%MOD;

    return r;
}

Matrix power(Matrix base,long long exp)
{
    Matrix result= {1,0,0,1};

    while(exp)
    {
        if(exp&1)
            result=multiply(result,base);

        base=multiply(base,base);
        exp>>=1;
    }

    return result;
}

int main()
{


    long long K;
    fin>>K;

    if(K==0)
    {
        fout<<0;
        return 0;
    }

    Matrix Z= {0,1,1,1};

    Matrix P=power(Z,K);

    fout<<P.b;

    return 0;
}