#include <stdio.h>
#include <stdlib.h>

#define MOD 666013
#define FILE_IN "kfib.in"
#define FILE_OUT "kfib.out"

long long int m[2] = {0, 1};
long long int z[4] = {0, 1,
                      1, 1};
long long int i[4] = {1, 0,
                      0, 1};

long long int* multMatrix2(long long int *a, long long int *b) {
    long long int *result = malloc(4 * sizeof(long long int));
    result[0] = (a[0] * b[0] + a[1] * b[2]) % MOD;
    result[1] = (a[0] * b[1] + a[1] * b[3]) % MOD;
    result[2] = (a[2] * b[0] + a[3] * b[2]) % MOD;
    result[3] = (a[2] * b[1] + a[3] * b[3]) % MOD;
    return result;
}

void printMatrix2(long long int *mat) {
    for(int i = 0; i < 4; i++) {
        printf("%lld ", mat[i]);
        if(i == 1) printf("\n");
    }
    printf("\n");
}

long long int* exponentiateMatrix2(long long int *mat, int n) {
    if(n == 0) {
        return i;
    }

    long long int *mat2 = multMatrix2(mat, mat);
    if(n % 2) {
        long long int *matAux = exponentiateMatrix2(mat2, (n - 1) / 2);
        return multMatrix2(mat, matAux);
    }
    else {
        return exponentiateMatrix2(mat2, n / 2);
    }
}

int main()
{
    FILE *fileIn = fopen(FILE_IN, "r"),
         *fileOut = fopen(FILE_OUT, "w");
    int k;

    fscanf(fileIn, "%d", &k);
    if(k == 0) {
        fprintf(fileOut, "0");
        return 0;
    }
    long long int *mat = exponentiateMatrix2(z, k - 1);
    long long result = (m[0] * mat[1] + m[1] * mat[3]) % MOD;
    fprintf(fileOut, "%lld\n", result);

    fclose(fileIn);
    fclose(fileOut);

    return 0;
}