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

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

const int mod = 666013;

void multiply(long long F[2][2], long long M[2][2]) {
    long long f1,f2,f3,f4;
    f1 = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % mod;
    f2 = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % mod;
    f3 = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % mod;
    f4 = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % mod;

    F[0][0] = f1;
    F[0][1] = f2;
    F[1][0] = f3;
    F[1][1] = f4;
}

void putere(long long F[2][2], int n) {
    long long M[2][2] = {{0,1}, {1,1}};
    if (n == 0 || n == 1)
        return;
    putere(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0)
        multiply(F, M);
}

long long fibonacci(int n) {
    long long F[2][2] = {{0,1},{1, 1}};
    if (n == 0)
        return 0;
    putere(F, n-1);
    return F[1][1];
}

int main() {
    int n;
    fin >> n;
    fout << fibonacci(n);
    return 0;
}