// kfib.cpp : This file contains the 'main' function. Program execution begins and ends there.
//


#include <iostream>
#include <fstream>

using namespace std;

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

class matrice {
public:
    int m[2][2];
    matrice() {
        memset(m, 0, sizeof(m));
    }
    void operator *=(const matrice& b) {
        matrice c;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    c.m[i][j] = (c.m[i][j] + ((1LL * m[i][k] * b.m[k][j]) % 666013)) % 666013;

        *this = c;
    }
};

void pow(matrice a, int b) {
    matrice p;
    p.m[0][0] = 1;
    p.m[1][1] = 1;
    for (; b; b >>= 1) {
        if (b & 1) p *= a;
        a *= a;
    }
    cout << p.m[0][1];
}

int main() {
    int n;
    in >> n;
    matrice a;
    a.m[0][0] = 1;
    a.m[1][0] = 1;
    a.m[0][1] = 1;
    pow(a, n);
    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file