#include <iostream>
#include <fstream>

#define MOD 666013

void multiply(long long a[2][2], long long b[2][2], long long res[2][2]) {
    res[0][0] = ((a[0][0] * b[0][0]) % MOD + (a[0][1] * b[1][0]) % MOD) % MOD;
    res[0][1] = ((a[0][0] * b[0][1]) % MOD + (a[0][1] * b[1][1]) % MOD) % MOD;
    res[1][0] = ((a[1][0] * b[0][0]) % MOD + (a[1][1] * b[1][0]) % MOD) % MOD;
    res[1][1] = ((a[1][0] * b[0][1]) % MOD + (a[1][1] * b[1][1]) % MOD) % MOD;
}

void copy(long long a[2][2], long long b[2][2]) {
    a[0][0] = b[0][0];
    a[0][1] = b[0][1];
    a[1][0] = b[1][0];
    a[1][1] = b[1][1];
}

void fastExponentiation(long long a[2][2], long long n, long long res[][2]) {
    long long temp[2][2] = {{1, 1},
                            {1, 1}};
    while (n) {
        if (n % 2 == 1) {
            multiply(res, a, temp);
            copy(res, temp);
        }
        multiply(a, a, temp);
        copy(a, temp);
        n /= 2;
    }
}

void getFiboNum(long long k, long long a[2][2]) {
    long long res[2][2] = {{1, 0},
                           {0, 1}};
    fastExponentiation(a, k - 1, res);
    std::cout << res[1][1] << std::endl;
}

int main() {
    std::ifstream fin("kfib.in");

    long long k;
    long long a[2][2] = {{0, 1},
                         {1, 1}};
    fin >> k;
    getFiboNum(k, a);
}