#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int mod = 666013;

struct matr {
    int elems[2][2];

    matr() {
        elems[0][1] = elems[1][1] = elems[0][0] = elems[1][0] = 0;
    }
    matr(int a11, int a12, int a21, int a22) {
        elems[0][0] = a11;
        elems[1][0] = a21;
        elems[0][1] = a12;
        elems[1][1] = a22;
    }
};

matr mul(matr a, matr b) {
    matr rez;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                rez.elems[i][j] += (1LL * a.elems[i][k] * b.elems[k][j]) % mod;

    return rez;
}

matr pow(matr a, int n) {
    if (n == 0)
        return matr(1, 0, 0, 1);
    if (n == 1)
        return a;
    if (n % 2 == 0) {
        //mul(pow(a, n/2), pow(a, n/2));
        return mul(pow(a, n/2), pow(a, n/2));
    } else {
        //mul(pow(a, n/2), pow(a, n/2));
        return mul(a, mul(pow(a, n/2), pow(a, n/2)));
    }
}

void print(matr a) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++)
            cout << a.elems[i][j] << " ";
        cout << endl;
    }
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    int n; cin >> n;

    matr rez, a, m;
    m.elems[0][0] = m.elems[1][0] = m.elems[1][1] = 0; m.elems[0][1] = 1;
    a.elems[0][0] = 0; a.elems[0][1] = a.elems[1][0] = a.elems[1][1] = 1;

    if (n == 0)
        cout << 0;
    else {
        m = mul(m, pow(a, n-1));
        //print(m);
        cout << m.elems[0][1];
    }

    return 0;
}