#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define mod 666013

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

void inmultire_matrici(int a[2][2], int b[2][2], int c[2][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c[i][j] += (1LL * a[i][k] * b[k][j]) % mod;
            }
        }
    }
}

void copiere_matrice(int a[2][2], int b[2][2]) {
    a[0][0] = b[0][0];
    a[0][1] = b[0][1];
    a[1][0] = b[1][0];
    a[1][1] = b[1][1];
}
void putere(int x[2][2], int p, int R[2][2]) {
    int aux[2][2];
    R[0][1] = R[1][0] = 0;
    R[0][0] = R[1][1] = 1;

    for (int i = 1; i <= p; i <<= 1) {
        if ((i & p)) {
            inmultire_matrici(R, x, aux);
            copiere_matrice(R, aux);
        }
        inmultire_matrici(x, x, aux);
        copiere_matrice(x, aux);
    }
}

int main() {
    int n;
    f>>n;

    int z[2][2], rez[2][2];

    z[0][0] = 0;
    z[0][1] = z[1][0] = z[1][1] = 1;

    putere(z, n - 1, rez);

    g<<rez[1][1];

    return 0;
}