#include <stdio.h>

using namespace std;

FILE* fin;
FILE* fout;
int k;

void MatrixMultiply(unsigned long long A[2][2], unsigned long long B[2][2])
{
    //printf("Multiplying matrix:\n%llu %llu\n%llu %llu\nWith:\n%llu %llu\n%llu %llu\n", A[0][0], A[0][1], A[1][0], A[1][1], B[0][0], B[0][1], B[1][0], B[1][1]);

    unsigned long long C[2][2];
    C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
    C[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
    C[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1];
    C[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1];
    A[0][0] = C[0][0] % 666013;
    A[0][1] = C[0][1] % 666013;
    A[1][0] = C[1][0] % 666013;
    A[1][1] = C[1][1] % 666013;
}
/*
void print(unsigned long long A[2][2], int i)
{
    printf("%d: %llu %llu %llu %llu\n", i, A[0][0], A[0][1], A[1][0], A[1][1]);
}
*/

void raiseTo(unsigned long long A[2][2], int n)
{
    if(n > 1)
    {

        int i;
        for(i = 2; i <= n; i *= 2)
        {
            MatrixMultiply(A, A);
            //print(A, i);
        }

        if(i / 2 < n)
        {
            //printf("Computing power %d\n", n - (i / 2));
            unsigned long long B[2][2] = {{0, 1}, {1, 1}};
            raiseTo(B, n - (i / 2));
            MatrixMultiply(A, B);
        }
    }
}

int main()
{
    fin = fopen("kfib.in", "r");
    fout = fopen("kfib.out", "w");
    fscanf(fin, "%d", &k);
    --k;
    unsigned long long A[2][2] = {{0, 1}, {1, 1}};
    raiseTo(A, k);
    //print(A, k);

    fprintf(fout, "%llu", A[1][1]);

    return 0;
}