#include <fstream>

#define mod1 666013

using namespace std;

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

long long a[5][5], sol[5][5], c[5][5];

inline void Inmultire(long long a1[][5], long long a2[][5]) {
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            c[i][j] = 0;
            for (int k = 1; k <= 2; k++) {
                c[i][j] += (a1[i][k] * a2[k][j]) % mod1;
                c[i][j] %= mod1;
            }
        }
    }

    a1[1][1] = c[1][1]; a1[1][2] = c[1][2]; a1[2][1] = c[2][1]; a1[2][2] = c[2][2];
}

inline void Ridicare(int n) {
    while (n) {
        if (n & 1) {
            Inmultire(sol, a);
            n--;
        }
        Inmultire(a, a); n >>= 1;
    }
}

inline void Read() {
    int N;

    fin >> N;

    a[1][1] = 0; a[1][2] = 1; a[2][1] = a[2][2] = 1;

    for (int i = 1; i <= 2; i++)
        sol[i][i] = 1;
    Ridicare(N - 1);

    fout << (sol[2][2]) % mod1;
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}