#include <bits/stdc++.h>

#define int long long
#define pii pair<int, int>
#define fs first
#define sd second

using namespace std;

const string fileName = "kfib";
ifstream in(fileName + ".in");
ofstream out(fileName + ".out");

struct mat {
    int n;
    int val[10][10];
};

const int MOD = 666013;

void unitate(mat &a, int lat);
mat prodMat(mat a, mat b);
mat binPow(mat base, int exp);

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); in.tie(nullptr);

    int n; in >> n;
    mat a;
    a.n = 2;
    a.val[1][1] = 0;
    a.val[1][2] = 1;
    a.val[2][1] = 1;
    a.val[2][2] = 1;

    // out << n << '\n';

    a = binPow(a, n);
    out << a.val[1][2] << '\n';

    return 0;
}

void unitate(mat &a, int lat) {
    a.n = lat;
    for(int i = 1; i <= a.n; i++) {
        for(int j = 1; j <= a.n; j++) {
            a.val[i][j] = 0;
        }
        a.val[i][i] = 1;
    }
}

mat prodMat(mat a, mat b) {
    mat c;
    c.n = a.n;
    for(int i = 1; i <= c.n; i++) {
        for(int j = 1; j <= c.n; j++) {
            c.val[i][j] = 0;
            for(int k = 1; k <= c.n; k++) {
                c.val[i][j] += a.val[i][k] * b.val[k][j] % MOD;
                c.val[i][j] %= MOD;
            }
        }
    }
    return c;
}

mat binPow(mat base, int exp) {
    mat p;
    if(exp == 0) {
        unitate(p, base.n);
        return p;
    }
    p = binPow(base, exp / 2);
    if(exp % 2 == 1) {
        p = prodMat(p, p);
        p = prodMat(p, base);
    /*
        for(int i = 1; i <= 2; i++) {
            for(int j = 1; j <= 2; j++) {
                out << p.val[i][j] << ' ';
            }
            out << '\n';
        }
        out << '\n';
    */
        return p;
    }
    else {
        p = prodMat(p, p);
        return p;
    }
}