#include <iostream>
#include <fstream>

using namespace std;

class Matrix
{
public:
    Matrix()
        : a{ 0 }, b{ 1 }
        , c{ 1 }, d{ 1 }
    {}

    void MakeI() { a = 1;b = 0;c = 0;d = 1;}

    Matrix operator * (Matrix const &obj) {
        Matrix res;
        res.a = ((a * obj.a) % 666013 + (b * obj.c) % 666013) % 666013;  // first line * first column
        res.b = ((a * obj.b) % 666013 + (b * obj.d) % 666013) % 666013;  // first line * second column
        res.c = ((c * obj.a) % 666013 + (d * obj.c) % 666013) % 666013;  // second line * first column
        res.d = ((c * obj.b) % 666013 + (d * obj.d) % 666013) % 666013;  // Second line * second column
        return res;
    }

    long long a, b;
    long long c, d;
};

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    uint32_t k;
    in >> k;

    Matrix a, r;
    r.MakeI();

    for (int i = 31;i >= 0;i--)
    {
        if (k & 1 << i)
            r = r * r * a;
        else
            r = r * r;
    }

    out << r.b;
}