#include <iostream>
using namespace std;

const long long MOD = 666013;

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

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    long long k;
    cin >> k;
    k--;

    long long rez[2][2] = {{1, 0}, {0, 1}};
    long long acc[2][2] = {{0, 1}, {1, 1}};

    while (k != 0) {
        if (k & 1) {
            mul(rez, acc);
        }

        mul(acc, acc);
        k = k >> 1;
    }

    cout << rez[1][1];
}