#include <bits/stdc++.h>
using namespace std;

const int MOD = 666013;
int k, z[3][3], m[3][3];

void prod(int a[3][3], int b[3][3]) {
    long long res[3][3];
    memset(res, 0, sizeof(res));
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            for (int k = 1; k <= 2; ++k) {
                res[i][j] += 1ll * a[i][k] * b[k][j] % MOD;
                res[i][j] %= MOD;
            }
        }
    }
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            a[i][j] = res[i][j];
        }
    }
}

void exp(int a[3][3], int pwr) {
    int res[3][3];
    memset(res, 0, sizeof(res));
    res[1][1] = res[2][2] = 1;
    while (pwr != 0) {
        if (pwr & 1) {
            prod(res, a);
        }
        prod(a, a);
        pwr >>= 1;
    }
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            a[i][j] = res[i][j];
        }
    }
}

int main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    cin >> k;
    z[1][2] = z[2][1] = z[2][2] = 1;
    m[1][2] = 1;
    exp(z, k - 1);
    prod(m, z);
    cout << m[1][2];
}