#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAXK = 1e9;
const int MOD = 666013;

struct matrice {
    int m[2][2]; // M2

    matrice() { memset(m, 0, sizeof(m)); }

    matrice(initializer_list<initializer_list<int>> init) {
        int i = 0;
        for (auto row: init) {
            int j = 0;
            for (auto col: row)
                m[i][j++] = col;
            i++;
        }
    }

    matrice operator * (matrice b) {
        matrice rez;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    rez.m[i][j] = (rez.m[i][j] + 1LL * m[i][k] * b.m[k][j] % MOD) % MOD;
        return rez;
    }
};

matrice fast_expo(matrice a, int b) {
    matrice rez = {
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1}
    }; // <=> rez = 1

    while (b) {
        if (b & 1) rez = rez * a;
        a = a * a;
        b >>= 1;
    }

    return rez;
}

int k;

int main() {
    in >> k;
    if (k <= 1) out << 1;
    else if (k == 2) out << 2;
    else {
        matrice fibo = {
            {1, 1},
            {1, 0}
        };

        matrice r = fast_expo(fibo, k);
        out << r.m[0][1];
    }

    return 0;
}