#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int P = 666013;
int _norm(int x) { return x >= P ? x - P : x < 0 ? x + P : x; }
struct Z {
    int x;
    Z(int x = 0) : x(_norm(x)) {}
    friend Z operator + (const Z &a, const Z &b) {
        return _norm(a.x + b.x);
    }
    friend Z operator * (const Z &a, const Z &b) {
        return 1ll * a.x * b.x % P;
    }
};
template <typename T, int N>
struct Matrix {
    array<array<T, N>, N> a;
    Matrix(T x = 0) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                a[i][j] = (i == j ? x : 0);
    }
    array<T, N>& operator[](int i) { return a[i]; }
    friend Matrix operator* (Matrix &a, Matrix &b) {
        Matrix c;
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < N; k++) {
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
};
template <typename T>
T quick_pow(T a, int b) {
    T res(1);
    while (b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

// #define HOME

int main() {
#ifndef HOME
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
#endif
    int n;
    Matrix<Z, 2> m;
    m[0] = {0, 1};
    m[1] = {1, 1};
    cin >> n;
    m = quick_pow(m, n);
    cout << m[0][1].x << "\n";
    return 0;
}