#include <fstream>
using namespace std;

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

const long long mod = 666013;

// o matrice 2 * 2
struct matrice
{
    long long a[2][2];
};

// inmultirea a doua matrici 2 * 2, totul mod 666013
matrice inmultire(matrice x, matrice y)
{
    matrice rez;

    rez.a[0][0] = (x.a[0][0] * y.a[0][0] + x.a[0][1] * y.a[1][0]) % mod;
    rez.a[0][1] = (x.a[0][0] * y.a[0][1] + x.a[0][1] * y.a[1][1]) % mod;
    rez.a[1][0] = (x.a[1][0] * y.a[0][0] + x.a[1][1] * y.a[1][0]) % mod;
    rez.a[1][1] = (x.a[1][0] * y.a[0][1] + x.a[1][1] * y.a[1][1]) % mod;

    return rez;
}

int main()
{
    long long k;
    fin >> k;

    // cazurile mici le tratez separat ca sa nu fie probleme cu matricea la puterea 0
    if (k == 0)
    {
        fout << 0;
        return 0;
    }
    if (k == 1)
    {
        fout << 1;
        return 0;
    }

    matrice z;
    z.a[0][0] = 1;
    z.a[0][1] = 1;
    z.a[1][0] = 1;
    z.a[1][1] = 0;

    matrice rezultat;
    rezultat.a[0][0] = 1;
    rezultat.a[0][1] = 0;
    rezultat.a[1][0] = 0;
    rezultat.a[1][1] = 1;

    long long putere = k - 1;

    while (putere > 0)
    {
        if (putere % 2 == 1)
            rezultat = inmultire(rezultat, z);

        z = inmultire(z, z);
        putere = putere / 2;
    }

    fout << rezultat.a[0][0];

    return 0;
}