#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>

#define M 666013

using namespace std;

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

typedef long long ll;

typedef vector<vector<ll>> matrix;
// a matrix is of shape nxn

matrix multiply_matrix(matrix a, matrix b) {
    int n1 = a.size(), m1 = a[0].size(), n2 = b.size(), m2 = b[0].size();
    if (m1 != n2) {
        cout << "Matrixes cannot be multiplied";
        exit(0);
    }

    matrix c;
    c.assign(n1, vector<ll>(m2, 0));

    for (int i = 0; i < n1; ++i) {
        for (int j = 0; j < m2; ++j) {
            ll sum = 0;
            for (int k = 0; k < n2; ++k) {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum % M;
        }
    }
    return c;
}

matrix matrix_power(matrix a, int power) {
    if (power == 1) {
        return a;
    }

    matrix b = matrix_power(a, power / 2);
    matrix c = power % 2 ? multiply_matrix(multiply_matrix(b, b), a) : multiply_matrix(b, b);
    
    int n = c.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            c[i][j] %= M;
        }
    }

    return c;
}

void Solve() {
    matrix dp;
    dp.assign(2, vector<ll>(2, 0));
    dp[0][1] = dp[1][0] = dp[1][1] = 1;

    int n;
    fin >> n;
    if (n <= 1) {
        fout << n;
        return;
    }

    matrix initial_values;
    initial_values.assign(1, vector<ll>(2, 0));
    initial_values[0][1] = 1;

    matrix fibbonaci = multiply_matrix(initial_values, matrix_power(dp, n));
    fout << fibbonaci[0][0];
}

int main() {

    ios_base::sync_with_stdio(false);

    Solve();

    return 0;
}