#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef long long LL;
const LL MOD = 666013;
struct matrice
{
    LL a11,a12,a21,a22;

};
matrice A, R;
matrice produs(matrice A, matrice B)
{
    matrice C;
    C.a11=(A.a11*B.a11+A.a12*B.a21) % MOD;
    C.a12=(A.a11*B.a12+A.a12*B.a22) % MOD;
    C.a21=(A.a21*B.a11+A.a22*B.a21) % MOD;
    C.a22=(A.a21*B.a12+A.a22*B.a22) % MOD;
    return C;


}
matrice putere(int e)
{
    matrice X;
    if(e==0)
    {
        X.a11=X.a22=1;
        X.a12=X.a21=0;
        return X;
    }
    X=putere(e/2);
    X=produs(X,X);
    if(e%2==1)X=produs(X,A);
    return X;
}
int main()
{
    int k;
    f>>k;
    A.a11=A.a12=A.a21=1;
    A.a22=0;
    R=putere(k);
    g<<R.a12;
    return 0;
}