#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)) {}
    Z operator + (const Z &b) const {
        return _norm(x + b.x);
    }
    Z operator * (const Z &b) const {
        return 1ll * x * b.x % P;
    }
};
template <typename R, int N>
struct Matrix {
    array<array<R, N>, N> a;
    Matrix(R x = 0) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                a[i][j] = (i == j ? x : 0);
    }
    array<R, N>& operator [](int i) { return a[i]; }
    Matrix operator *(Matrix other) {
        Matrix res;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    res[i][j] = res[i][j] + a[i][k] * other[k][j];
        return res;
    }
};

template <typename T>
T quick_pow(T a, long long b) {
    T res(1);
    while (b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

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