#include <vector>
#include <fstream>
using namespace std;

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

const int mod = 666013;

int n;

void atrib(int a[][2], int x) {
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = x;
}

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

void atrib(int a[][2], int b[][2]) {
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = b[i][j];
}

int main() {
    fin >> n;
    n--;
    int sol[2][2] = {{1, 0}, {0, 1}}, aux[2][2] = {{0, 1}, {1, 1}};
    for (int i = 1; i <= n; i <<= 1) {
        if (i & n) {
            int now[2][2];
            atrib(now, 0);
            multiply(now, sol, aux);
            atrib(sol, now);
        }
        int now[2][2];
        atrib(now, 0);
        multiply(now, aux, aux);
        atrib(aux, now);
    }
    fout << sol[1][1];
}