#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

struct Matrix
{
    int a11, a12, a21, a22;
    Matrix()
    {
        a11 = 1;
        a12 = 0;
        a21 = 0;
        a22 = 1;
    }
    Matrix(int v11, int v12, int v21, int v22)
    {
        a11 = v11;
        a12 = v12;
        a21 = v21;
        a22 = v22;
    }
};
Matrix operator*(Matrix, Matrix);
Matrix A, S;
int k;

int main()
{
    A = Matrix(0, 1, 1, 1);
    f>>k;
    for(;k;k>>=1)
    {
        if(k&1)
            S = S*A;
        A = A*A;
    }
    g<<S.a12<<'\n';
    return 0;
}

Matrix operator*(Matrix A, Matrix B)
{
    Matrix R;
    R.a11 = (1LL*A.a11*B.a11+1LL*A.a12*B.a21)%666013;
    R.a12 = (1LL*A.a11*B.a12+1LL*A.a12*B.a22)%666013;
    R.a21 = (1LL*A.a21*B.a11+1LL*A.a22*B.a21)%666013;
    R.a22 = (1LL*A.a21*B.a12+1LL*A.a22*B.a22)%666013;
    return R;
}