#include <bits/stdc++.h>

using namespace std;
#define int long long int
#define pb push_back
#define sz(x) (int)(x.size())
#define all(a) a.begin(), a.end()
#define nl '\n'
const int N = 3e5 + 5, INF = 1e9, mod = 666013;

int k, a[3][3], b[3][3], c[3][3];

void inm(int a[3][3], int b[3][3]) {
    int c[3][3];
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            c[i][j] = 0;
        }
    }
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            for (int k = 1; k <= 2; k++) {
                c[i][j] += a[i][k] * b[k][j] % mod;
                c[i][j] %= mod;
            }
        }
    }
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}

void pw(int a[3][3], int n) {
    int res[3][3];
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            res[i][j] = 0;
        }
    }
    res[1][1] = res[2][2] = 1; /// matrice care e ca 1 
    while (n) {
        if (n % 2 == 1) {
            inm(res, a);
        }
        inm(a, a);
        n /= 2;
    }
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
            a[i][j] = res[i][j];
        }
    }
}

signed main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    cin >> k;
    c[1][2] = c[2][2] = c[2][1] = 1;
    a[1][1] = a[1][2] = 1;
    pw(c, k - 1);
    inm(a, c);
    cout << a[1][1];
}