//Kfib

#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void expAk(long long v[4], int K) { //v[0] = A[0][0], v[1] = A[0][1], v[2] = A[1][0], v[3] = A[1][1]
    if(K == 1) { v[0] = 0; v[1] = v[2] = v[3] = 1; return; }
    long long aux[4];
    if(K%2 == 0) {
        expAk(v, K/2);
        aux[0] = (v[0]*v[0] + v[1]*v[2])%666013;
        aux[1] = (v[0]*v[1] + v[1]*v[3])%666013;
        aux[2] = (v[2]*v[0] + v[3]*v[2])%666013;
        aux[3] = (v[2]*v[1] + v[3]*v[3])%666013;
        v[0] = aux[0]; v[1] = aux[1]; v[2] = aux[2]; v[3] = aux[3];
        return;
    }
    if(K%2 == 1) {
        expAk(v, K-1);
        aux[0] = v[1]%666013;
        aux[1] = (v[0] + v[1])%666013;
        aux[2] = v[3]%666013;
        aux[3] = (v[2] + v[3])%666013;
        v[0] = aux[0]; v[1] = aux[1]; v[2] = aux[2]; v[3] = aux[3];
        return;
    }
}

int main()
{
    long long v[4];
    int K;

    fin>>K;

    expAk(v, K-1);

    fout<<v[3]%666013;

    fin.close();
    fout.close();

    return 0;
}