#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;
const int MOD = 666013;

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

class Matrix {
public:
    vector<vector<int>> mat;
    int n;

    Matrix(int size, bool flag = false) : n(size) {
        mat.assign(n, vi(n, 0));
        if (flag) {
            for (int i = 0; i < n; i++)
                mat[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix &other) const {
        Matrix result(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result.mat[i][j] = (result.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return result;
    }

    Matrix& operator*=(const Matrix &other) {
        *this = *this * other;
        return *this;
    }

    Matrix pow(long long exp) const {
        Matrix result(n, true), base = *this;
        while (exp) {
            if (exp & 1)
                result = result * base;
            base *= base;
            exp >>= 1;
        }
        return result;
    }
};
int kth_term (int k) {
    Matrix A(2);
    A.mat = {{1, 1}, {1, 0}};
    return A.pow(k - 1).mat[0][0];
}
signed main() {
    int k;
    fin >> k;
    fout << kth_term(k) << '\n';
    return 0;
}