#include <bits/stdc++.h>

std::ifstream fin("kfib.in");
std::ofstream fout("kfib.out");

const int MOD = 666013;
const int DIM = 3;

int64_t A[DIM][DIM], B[DIM][DIM];
int n;

void unitate(int64_t B[][DIM]) {
    // B <- I_2
    int i, j;
    for (i = 1; i < DIM; i++) {
        for (j = 1; j < DIM; j++)
            B[i][j] = 0;
        B[i][i] = 1;
    }
}

void atrib(int64_t A[][DIM], int64_t B[][DIM]) {
    // A <- B
    int i, j;
    for (i = 1; i < DIM; i++)
        for (j = 1; j < DIM; j++)
            A[i][j] = B[i][j];
}

void inmult(int64_t C[][DIM], int64_t A[][DIM], int64_t B[][DIM]) {
    // C <- A * B
    int i, j, k;
    for (i = 1; i < DIM; i++)
        for (k = 1; k < DIM; k++) {
            C[i][k] = 0;
            for (j = 1; j < DIM; j++)
                C[i][k] = (C[i][k] + (int64_t)A[i][j] * B[j][k]) % MOD;
        }
}

void exp(int n, int64_t A[][DIM], int64_t B[][DIM]) {
    // B <- A^n
    int64_t C[DIM][DIM];
    unitate(B);
    while (n > 0) {
        if (n & 1) {
            inmult(C, A, B);
            atrib(B, C);        
        }
        inmult(C, A, A);
        atrib(A, C);
        n >>= 1;    
    }
}

int main() {
    fin >> n;
    A[1][1] = 0; A[1][2] = 1;
    A[2][1] = 1; A[2][2] = 1;
    exp(n, A, B);
    fout << B[1][2] << "\n";
    
    fin.close();
    fout.close();
    
    return 0;
}