#include <bits/stdc++.h>

using namespace std;
const int NMAX = 102;
const int MOD = 666013;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

class Matrix {

    vector < vector <int> > matrix;
    int n, m;

public:

    Matrix (int n, int m) {
        this->n = n;
        this->m = m;
        this->matrix.resize(n);
        for (int i = 0; i < n; i++)
            this->matrix[i].resize(m, 0);
    }

    Matrix(int n, int m, vector < vector < int > > &matrix) {
        this->n = n;
        this->m = m;
        this->matrix = matrix;
    }

    ~Matrix()
     {
         for(int i = 0; i < n; i++)
            matrix[i].clear();
        matrix.clear();
     }

    void Print() {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++)
                cout << matrix[i][j] << ' ';
            cout << '\n';
        }
    }

    Matrix operator* (Matrix &mat) {
        vector < vector <int> > ans_matrix;
        ans_matrix.resize(n);
        for(int i = 0; i < n; i++) {
            ans_matrix[i].resize(mat.m, 0);
            for(int j = 0; j < mat.m; j++)
                for(int k = 0; k < mat.n; k++)
                    ans_matrix[i][j] = ( 1LL * ans_matrix[i][j] + 1LL * matrix[i][k] * mat.matrix[k][j]) % MOD;
        }

        return Matrix(n, mat.m, ans_matrix);
    }

    vector <int> &operator[] (int index) {
        return matrix[index];
    }

    Matrix operator^ (int p) {
        Matrix ans(n, m);
        Matrix base = *this;
        for(int i = 0; i < n; i++)
            ans[i][i] = 1;
        for(int bits = 0; bits < 31; bits++) {
             if(p & (1 << bits))
                ans = ans * base;
            base = base * base;
        }

        return ans;
    }


};

int main() {
    int k;
    vector <vector <int>> mat;
        mat.push_back(vector<int>({1, 1}));
        mat.push_back(vector<int>({1, 0}));


    Matrix matrixBase(mat.size(), mat[0].size(), mat);

    fin >> k;

    if (k == 0)
        fout << 0;
    else if (k == 1)
        fout << 1;
    else {
        --k;
        Matrix matrixAns = (matrixBase^k);
        fout << matrixAns[0][0];
    }

    return 0;
}