#include <stdio.h>

#define MOD 666013LL

typedef struct {
    long long a[2][2];
} Matrix;

Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++) {
            C.a[i][j] = 0;
            for (k = 0; k < 2; k++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
        }
    return C;
}

Matrix matpow(Matrix M, long long exp) {
    /* rezultat = matricea identitate */
    Matrix result;
    result.a[0][0] = 1; result.a[0][1] = 0;
    result.a[1][0] = 0; result.a[1][1] = 1;

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

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

    long long k;
    fscanf(fin, "%lld", &k);

    /* cazuri de baza */
    if (k == 0) {
        fprintf(fout, "0\n");
    } else if (k == 1) {
        fprintf(fout, "1\n");
    } else {
        Matrix Z;
        Z.a[0][0] = 0; Z.a[0][1] = 1;
        Z.a[1][0] = 1; Z.a[1][1] = 1;

        Matrix R = matpow(Z, k);
        /* R = Z^k, iar R.a[0][1] = F(k) */
        fprintf(fout, "%lld\n", R.a[0][1]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}