#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
const lli MODULO = 666013;

int t, n, k;

lli my_pow(lli b, lli p)
{
    if (p == 0) return 1;
    if (p == 1) return b;

    if (p % 2 == 0) return my_pow(b * b % MODULO, p / 2) % MODULO;
    return b * my_pow(b * b % MODULO, (p - 1) / 2) % MODULO;
}

struct matrix {
    int rows, cols;
    lli data[5][5]; // in a real world program should be dynamically allocated

    void multiply(matrix another, matrix &output) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < another.cols; j++) {
                lli aux = 0;
                for (int k = 0; k < cols; k++) {
                    aux += data[i][k] * another.data[k][j];
                    aux %= MODULO;
                }
                output.data[i][j] = aux;
            }
        }

        output.rows = rows;
        output.cols = another.cols;
    }

    void copyto(matrix &output) {
        output.rows = rows;
        output.cols = cols;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                output.data[i][j] = data[i][j];
            }
        }
    }

    void power(int p, matrix &output) {
        output.rows = rows;
        output.cols = cols;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == j) {
                    output.data[i][j] = 1;
                } else {
                    output.data[i][j] = 0;
                }
            }
        }

        matrix base;
        matrix temp;
        copyto(base);

        for (int i = 0; (1 << i) <= p; i++) {
            if (((1 << i) & p) > 0) {
                base.multiply(output, temp);
                temp.copyto(output);
            }
            base.multiply(base, temp);
            temp.copyto(base);
        }
    }

    void show() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                cout << data[i][j] << " ";
            }cout << endl;
        }
    }
};

int main() {
    freopen("carici.in", "r", stdin);

    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    ios::sync_with_stdio(false);

    cin >> n;

    matrix Z;
    Z.rows = 2;
    Z.cols = 2;
    Z.data[0][0] = 0;
    Z.data[0][1] = Z.data[1][0] = Z.data[1][1] = 1;

    matrix Zpow;
    Z.power(n - 1, Zpow);

    matrix M0;
    M0.rows = 1;
    M0.cols = 2;
    M0.data[0][0] = 0;
    M0.data[0][1] = 1;

    matrix M;
    M0.multiply(Zpow, M);
    cout << M.data[0][1] << "\n";

    return 0;
}