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

using namespace std;

#define MOD 666013

void multiply(vector<vector<long long>>& A, vector<vector<long long>>& B) {
    vector<vector<long long>> C(2, vector<long long>(2));

    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;

    A[0][0] = C[0][0];
    A[0][1] = C[0][1];
    A[1][0] = C[1][0];
    A[1][1] = C[1][1];
}

vector<vector<long long>> fast_exp(vector<vector<long long>>& A, int pow) {
    vector<vector<long long>> p = {{1, 0}, {0, 1}};
    while (pow) {
        if (pow % 2 == 1) {
            multiply(p, A);
        }
        multiply(A, A);
        pow /= 2;
    }
    return p;
}

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

    int n;
    in >> n;
    vector<vector<long long>> A = {{1, 1}, {1, 0}};
    vector<vector<long long>> B = fast_exp(A, n);
    out << B[0][1];
}