#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];
}

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 = {{1, 1}, {1, 0}};

    for (int i = 0; i < n; i++) {
        multiply(A, B);
    }
    out << A[0][1];
}