#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

const int MOD = 666013;

int a[2][2], f[2][2];

void initialization() {
    a[0][1] = a[0][0] = a[1][0] = 1;
    f[0][0] = 1;
}

void multiplication(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] = (c[i][j] + (1LL * a[i][k]*b[k][j]) % MOD) % MOD;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}

void fast_exp(int n) {
    initialization();
    while (n) {
        if ((n&1)) {
            multiplication(f, a);
        }
        n = (n>>1);
        multiplication(a, a);
    }
}
int findKfib(int k) {
    fast_exp(k - 1);
    if (k == 0) return 0;
    return f[0][0];
}

int main() {
    int k;
    fin>>k;
    fout<<findKfib(k);

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