#include <bits/stdc++.h>

using namespace std;

int kModulo = 666013;

int main()
{
    int k;
    long long s0, s1, s2, s3;
    long long c0, c1, c2, c3;
    long long r0, r1, r2, r3;
    freopen("kfib.in", "rt", stdin);
    freopen("kfib.out", "wt", stdout);

    scanf("%d", &k);
    c0 = 0;
    c1 = c2 = c3 = 1;
    s0 = s3 = 1;
    s1 = s2 = 0;

    while (k) {
        if (k % 2) {
            r0 = s0 * c0 + s1 * c2;
            r1 = s0 * c1 + s1 * c3;
            r2 = s2 * c0 + s3 * c2;
            r3 = s2 * c1 + s3 * c3;
            s0 = r0 % kModulo;
            s1 = r1 % kModulo;
            s2 = r2 % kModulo;
            s3 = r3 % kModulo;
        }
        r0 = c0 * c0 + c1 * c2;
        r1 = c0 * c1 + c1 * c3;
        r2 = c2 * c0 + c3 * c2;
        r3 = c2 * c1 + c3 * c3;
        c0 = r0 % kModulo;
        c1 = r1 % kModulo;
        c2 = r2 % kModulo;
        c3 = r3 % kModulo;
        k >>= 1;
    }

    printf("%lld\n", s1);

    return 0;
}