#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

int n;
struct matr{

    long long el[3][3];
};

matr iMat;
void afisareMat(matr a){

    for(int i = 1; i<= 2; i++)
    {
        for(int j = 1; j<= 2; j++)
        {
            g<<a.el[i][j]<<" ";
        }
        g<<"\n";
    }
    g<<"\n";
}

matr inmultireMat(matr a, matr b){

    matr c;

    c.el[1][1] = (a.el[1][1] * b.el[1][1] + a.el[1][2] * b.el[2][1]) % MOD;
    c.el[1][2] = (a.el[1][1] * b.el[1][2] + a.el[1][2] * b.el[2][2]) % MOD;
    c.el[2][1] = (a.el[2][1] * b.el[1][1] + a.el[2][2] * b.el[2][1]) % MOD;
    c.el[2][2] = (a.el[2][1] * b.el[1][2] + a.el[2][2] * b.el[2][2]) % MOD;

    return c;
}

matr produs(int k){

    if(k==1)
        return iMat;

    matr m;
    if(k%2==0)
    {
        m = produs(k/2);
        return inmultireMat(m,m);
    }
    else
    {
        m = produs((k-1)/2);
        m = inmultireMat(m,m);
        return inmultireMat(m,iMat);
    }

}
int main()
{
    iMat.el[1][1]=1;
    iMat.el[1][2]=1;
    iMat.el[2][1]=1;
    iMat.el[2][2]=0;
    f>>n;
    if(n==0){

        g<<0;
        return 0;
    }
    else if (n<=2){

        g<<1;
        return 0;
    }

    matr fin = produs(n-2);

    //afisareMat(fin);

    g<<(fin.el[1][1] + fin.el[2][1]) % MOD;

    f.close();
    g.close();
    return 0;
}