#include <fstream>
using namespace std;

#define MOD 666013

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

int64_t kFib(int64_t k) {
    int64_t mat[2][2], aux[2][2], c[2][2];
    mat[0][0] = 0;
    mat[0][1] = mat[1][1] = mat[1][0] = 1;

    aux[0][1] = aux[1][0] = 0;
    aux[0][0] = aux[1][1] = 1;

    while (k) {
        if (k % 2) {
            /// c = aux * mat
            c[0][0] = (aux[0][0] * mat[0][0] + aux[0][1] * mat[1][0]) % MOD;
            c[0][1] = (aux[0][0] * mat[0][1] + aux[0][1] * mat[1][1]) % MOD;
            c[1][0] = (aux[1][0] * mat[0][0] + aux[1][1] * mat[1][0]) % MOD;
            c[1][1] = (aux[1][0] * mat[0][1] + aux[1][1] * mat[1][1]) % MOD;

            /// aux = c
            aux[0][0] = c[0][0];
            aux[0][1] = c[0][1];
            aux[1][0] = c[1][0];
            aux[1][1] = c[1][1];
        }
        /// c = mat * mat
        c[0][0] = (mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0]) % MOD;
        c[0][1] = (mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]) % MOD;
        c[1][0] = (mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0]) % MOD;
        c[1][1] = (mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]) % MOD;

        /// mat = c
        mat[0][0] = c[0][0];
        mat[0][1] = c[0][1];
        mat[1][0] = c[1][0];
        mat[1][1] = c[1][1];

        k /= 2;
    }

    return aux[1][0];
}

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

    fout << kFib(k);
}