#include <stdio.h>

#define MOD 666013

typedef struct {
    long long a, b, c, d;
} Mat;

Mat multiply(Mat x, Mat y) {
    Mat r;
    r.a = ((x.a * y.a) % MOD + (x.b * y.c) % MOD) % MOD;
    r.b = ((x.a * y.b) % MOD + (x.b * y.d) % MOD) % MOD;
    r.c = ((x.c * y.a) % MOD + (x.d * y.c) % MOD) % MOD;
    r.d = ((x.c * y.b) % MOD + (x.d * y.d) % MOD) % MOD;
    return r;
}

Mat exp_by_squaring(Mat base, long long exp) {
    Mat result;
    result.a = 1; result.b = 0;
    result.c = 0; result.d = 1;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        exp /= 2;
    }
    return result;
}

long long kFibTerm(int K) {
    if (K == 0) return 0;

    Mat m;
    m.a = 1; m.b = 1;
    m.c = 1; m.d = 0;

    Mat rez = exp_by_squaring(m, K);
    return rez.c;
}

int main() {
    int K;
    FILE *fin  = fopen("kfib.in",  "r");
    FILE *fout = fopen("kfib.out", "w");

    if (fscanf(fin, "%d", &K) == 1) {
        fprintf(fout, "%lld\n", kFibTerm(K));
    }

    fclose(fin);
    fclose(fout);
}