#include <iostream>

using namespace std;

#include <vector>
#include <iostream>
#include <fstream>

#define MOD 666013

class Solution {
public:
    int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        auto fib_matrix = getFibMatrixAtPow(n - 1);
        return fib_matrix[1][1];
    }

private:
    vector<vector<int>> getFibMatrixAtPow(int n) {
        vector<vector<int>> base(2, vector<int>(2, 1));
        base[0][0] = 0;

        vector<vector<int>> solution(2, vector<int>(2, 0));
        solution[0][0] = 1;
        solution[1][1] = 1;
        for (int k = 0; (1<<k) <= n; k++) {
            if ( (n & (1 << k)) > 0) {
                // n has the k-th bit set.
                solution = multiply(solution, base);
            }
            base = multiply(base, base);
        }
        return solution;
    }

    vector<vector<int>> multiply(const vector<vector<int>> m1, const vector<vector<int>> m2) {
        vector<vector<int>> solution(2, vector<int>(2, 0));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    solution[i][j] =
                        ((long long)solution[i][j] + (long long)m1[i][k] * m2[k][j]) % MOD;

                }
            }
        }
        return solution;
    }

};

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    int n;
    fin >> n;
    Solution sol;
    fout << sol.fib(n) << endl;

    return 0;
}