#include <bits/stdc++.h>
#define mod 666013
#define ll long long

using namespace std;

struct mat {
    int a[2][2];
    mat() {
        memset(a, 0, sizeof(a));
    }

    int getAns() {
        return a[0][0];
    }
};

int n;
mat i2, init, base;

mat mul(mat x, mat y) {
    mat ans;

    for (int k = 0; k < 2; ++k)
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                ans.a[i][j] = (1LL * x.a[i][k] * y.a[k][j] + ans.a[i][j]) % mod;

    return ans;
}

mat exp(mat x, int n) {
    if (n == 0) return i2;

    mat p = exp(x, n >> 1);
    if (n & 1) return mul(x, mul(p, p));
    return mul(p, p);
}

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

    i2.a[0][0] = i2.a[1][1] = 1;
    init.a[0][0] = init.a[1][0] = 1;
    base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;

    scanf("%d", &n);

    if (n == 0) printf("%d\n", 0);
    else if (n == 1) printf("%d\n", 1);
    else if (n == 2) printf("%d\n", 1);
    else printf("%d\n", (mul(init, exp(base, n - 1))).getAns());

    return 0;
}