#include <bits/stdc++.h>

using namespace std;

struct Matrix
{
    int a11, a12, a21, a22;

    void operator *= (Matrix &other)
    {
        *this = {(1LL * a11 * other.a11 + 1LL * a12 * other.a21) % 666013,
                 (1LL * a11 * other.a12 + 1LL * a12 * other.a22) % 666013,
                 (1LL * a21 * other.a11 + 1LL * a22 * other.a21) % 666013,
                 (1LL * a21 * other.a12 + 1LL * a22 * other.a22) % 666013};
    }

    void operator ^= (int power)
    {
        Matrix result = {1, 0,
                         0, 1};

        while(power)
        {
            if(power & 1) result *= *this;

            *this *= *this; power >>= 1;
        }

        *this = result;
    }
};

int K; Matrix M1 = {0, 1}, Z = {0, 1,
                                1, 1};

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%d", &K);

    Z ^= K; M1 *= Z;

    printf("%d", M1.a11);

    return 0;
}