#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define f first
#define s second
#define pb push_back
#define lsh(i) (1 << (i))
#define fori(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define fore(x, a) for(auto &(x): (a))

using namespace std;

const int N = 2, mod = 666013;

void multiply(vvi &Z, vvi B) {
    vvi A(Z);
    Z = vvi(N, vi(N, 0));
    fori(i, N)
        fori(j, N)
            fori(k, N)
                Z[i][j] = (Z[i][j] + 1ll * A[i][k] * B[k][j]) % mod;
}

void f(vvi &Z, int n) {

    vvi aux(Z);
    while(n) {
        if(n % 2)
            multiply(Z, aux);
        multiply(aux, aux);
        n /= 2;
    }

}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ifstream cin("kfib.in");
    ofstream cout("kfib.out");

    int n;
    cin >> n;

    if(n <= 1) {
        cout << n;
        return 0;
    }

    vvi Z = {{1, 1}, {1, 0}};
    vvi M = {{1, 0}, {0, 0}};

    f(Z, n - 2);
    multiply(Z, M);

    cout << Z[0][0] << '\n';


    return 0;

}