#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int MOD = 666013;

// Funcție pentru înmulțirea a două matrici
vector<vector<int>> multiply(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    int n = a.size();
    vector<vector<int>> result(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                result[i][j] = (result[i][j] + 1LL * a[i][k] * b[k][j] % MOD) % MOD;
            }
        }
    }
    return result;
}

// Funcție pentru exponentierea matricială
vector<vector<int>> matrix_pow(vector<vector<int>> base, int exp) {
    int n = base.size();
    vector<vector<int>> result(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) result[i][i] = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = multiply(result, base);
        base = multiply(base, base);
        exp /= 2;
    }
    return result;
}

// Funcție pentru a calcula al K-lea termen folosind matricea de tranziție
int calculate_kth_term(int K, const vector<int>& initial_terms,
                       const vector<int>& coefficients) {
    int m = coefficients.size();
    if (K < m) return initial_terms[K];

    // Construirea matricei de tranziție
    vector<vector<int>> transition_matrix(m, vector<int>(m, 0));
    for (int i = 0; i < m - 1; ++i) transition_matrix[i][i + 1] = 1;
    for (int j = 0; j < m; ++j) transition_matrix[m - 1][j] = coefficients[m - j - 1] % MOD;

    // Aplicăm exponentierea matricială
    transition_matrix = matrix_pow(transition_matrix, K - m + 1);

    // Calculăm al K-lea termen
    int result = 0;
    for (int i = 0; i < m; ++i) {
        result = (result + 1LL * transition_matrix[m - 1][i] * initial_terms[i] % MOD) % MOD;
    }
    return result;
}

int main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int K;
    //cout << "Introduceți valoarea lui K: ";
    cin >> K;
    K--;
    // Definim termenii inițiali și coeficienții relației de recurență
    vector<int> initial_terms = {1, 1}; // Ex. pentru Fibonacci
    vector<int> coefficients = {1, 1}; // Ex. pentru Fibonacci

  //  cout << "Al " << K << "-lea termen al șirului modulo " << MOD << " este: "
       cout  << calculate_kth_term(K, initial_terms, coefficients) << endl;

    return 0;
}