#include <bits/stdc++.h>
#define NMAX 4
#define MOD 666013
#define ll long long
#define ull unsigned long long

using namespace std;

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

int k;
ll sir[NMAX], a[NMAX][NMAX], b[NMAX][NMAX];

void unitate(int d, ll b[][NMAX]) {
    for (int i = 1; i <= d; i++) {
        b[i][i] = 1;
    }
}

void copiere(int d, ll dest[][NMAX], ll src[][NMAX]) {
    for (int i = 1; i <= d; i++) {
        for (int j = 1; j <= d; j++) {
            dest[i][j] = src[i][j];
        }
    }
}

void produs(int d, ll a[][NMAX], ll b[][NMAX], ll prod[][NMAX]) {
    for (int i = 1; i <= d; i++) {
        for (int j = 1; j <= d; j++) {
            prod[i][j] = 0;
            for (int k = 1; k <= d; k++) {
                prod[i][j] += 1LL * a[i][k] * b[k][j];
                prod[i][j] %= MOD;
            }
        }
    }
}

void fast_expo(int n, int d, ll a[][NMAX], ll b[][NMAX]) {
    ll c[NMAX][NMAX];
    unitate(d, b);

    while (n) {
        if (n & 1) {
            produs(d, a, b, c);
            copiere(d, b, c);
        }
        produs(d, a, a, c);
        copiere(d, a, c);
        n >>= 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> k;
    if (k == 0) {
        fout << 0;
        return 0;
    }
    if (k == 1) {
        fout << 1;
        return 0;
    }

    k++;
    sir[1] = 0;
    sir[2] = 1;
    a[1][1] = 0;
    a[1][2] = a[2][1] = a[2][2] = 1;

    fast_expo(k - 2, 2, a, b);

    fout << ((sir[1] * b[1][2]) % MOD + (sir[2] * b[2][2]) % MOD) % MOD;
    return 0;
}