#include <stdio.h>

#define MOD 666013LL
typedef long long ll;
typedef ll Mat[2][2];

void multiply(Mat A, Mat B, Mat C) {
    Mat tmp = {{0,0},{0,0}};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                tmp[i][j] = (tmp[i][j] + A[i][k] * B[k][j]) % MOD;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            C[i][j] = tmp[i][j];
}

void matpow(Mat M, long long exp, Mat result) {
    result[0][0] = result[1][1] = 1;
    result[0][1] = result[1][0] = 0;

    while (exp > 0) {
        if (exp & 1)
            multiply(result, M, result);
        multiply(M, M, M);
        exp >>= 1;
    }
}

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

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

    if (k == 0) {
        fprintf(fout, "0\n");
    } else {
        Mat M = {{1,1},{1,0}};
        Mat R;
        matpow(M, k, R);
        fprintf(fout, "%lld\n", R[0][1]); 
    }

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