#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;
using ll = long long int;

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

struct matrix {

    int nr_lines, nr_cols;
    ll m[3][3];
    matrix() : nr_lines(0), nr_cols(0) {}
};

matrix operator* (const matrix& m1, const matrix& m2) {

    matrix aux;
    aux.nr_lines = m1.nr_lines;
    aux.nr_cols = m2.nr_cols;

    for (int i = 1; i <= aux.nr_lines; i++)
    for (int j = 1; j <= aux.nr_cols; j++) {

        aux.m[i][j] = 0;

        for (int k = 1; k <= m1.nr_cols; k++)
            aux.m[i][j] += (m1.m[i][k] * 1LL * m2.m[k][j]) % MOD;
    }
    return aux;
}

int main() {

    int k;
    in >> k;
    in.close();

    if (k == 0)
        out << "0\n";
    else if (k == 1)
        out << "1\n";
    else {

        k--;
        matrix m, a, rez;

        m.nr_lines = 1;
        m.nr_cols = 2;
        m.m[1][1] = 0;
        m.m[1][2] = 1;

        rez.nr_lines = a.nr_lines = 2;
        rez.nr_cols = a.nr_cols = 2;
        a.m[1][1] = 0;
        a.m[1][2] = 1;
        a.m[2][1] = 1;
        a.m[2][2] = 1;
        rez.m[1][1] = 1;
        rez.m[1][2] = 0;
        rez.m[2][1] = 0;
        rez.m[2][2] = 1;


        for (int i = 0; (1 << i) <= k; i++)
        {
            if (k & (1 << i))
               rez = rez * a;
            a = a * a;
        }
        m = m * rez;
        out << m.m[1][2] % MOD << "\n";
    }
    out.close();
    return 0;
}