#include <iostream>
#include <fstream>

#define MOD 666013

using namespace std;

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

void inmultire_matrici(int a[3][3], int b[3][3], int c[3][3]) {
    c[0][0] = ((long long) a[0][0] * b[0][0] + (long long) a[0][1] * b[1][0]) % MOD;
    c[0][1] = ((long long) a[0][0] * b[0][1] + (long long) a[0][1] * b[1][1]) % MOD;
    c[1][0] = ((long long) a[1][0] * b[0][0] + (long long) a[1][1] * b[1][0]) % MOD;
    c[1][1] = ((long long) a[1][0] * b[0][1] + (long long) a[1][1] * b[1][1]) % MOD;
}

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

int t_fibonacci(int k) {
    int a[3][3] = {{1, 1},
                   {1, 0}}, put[3][3] = {{1, 0},
                                         {0, 1}}, aux[3][3];
    do {
        if (k % 2) {
            inmultire_matrici(put, a, aux);
            copiere(put, aux);
        }
        inmultire_matrici(a, a, aux);
        copiere(a, aux);
        k /= 2;
    } while (k);
    return put[0][1];
}

int main() {
    int k;
    f >> k;
    g << t_fibonacci(k);
    return 0;
}