#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

const int mod = 666013;

struct matrix {
    int a[2][2];
    matrix() {
        memset(a, 0, sizeof(a));
    }
    void get_null() {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                a[i][j] = 0;
            }
            a[i][i] = 1;
        }
    }
    matrix operator * (const matrix &other) {
        matrix answer;
        memset(answer.a, 0, sizeof(answer.a));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    answer.a[i][k] += (ll) a[i][j] * other.a[j][k] % mod;
                    answer.a[i][k] %= mod;
                }
            }
        }
        return answer;
    }
};

matrix power (matrix a, int b) {
    matrix p;
    p.get_null();
    while (b) {
        if (b & 1) {
            p = p * a;
        }
        a = a * a;
        b >>= 1;
    }
    return p;
}

signed main()
{
    int n;
    in >> n;
    matrix answer;
    answer.a[0][0] = 0;
    answer.a[0][1] = 1;
    answer.a[1][0] = 1;
    answer.a[1][1] = 1;

    answer = power(answer, n);
    out << answer.a[1][0];

    return 0;
}