#include<cstdio>
#include<cstring>
#define mod 666013
using namespace std;
typedef int matrice[3][3];
matrice MAT, SOL;
int n;
void mult (matrice A, matrice B, matrice C) {
    for (int i=0; i<2; ++i)
        for (int j=0; j<2; ++j)
            for (int k=0; k<2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
}
void power (int p, matrice M) {
    matrice AUX, C;

    memcpy(C, MAT, sizeof(MAT)); // Matricea C = Matricea MAT
    M[0][0] = M[1][1] = 1;

    for (int i=0; (1<<i)<=p; ++i) { // Luam toti biti lui p la rand
        if ((1<<i) & p) { // Daca bitul i din p este 1 numarul este impar
            memset(AUX, 0, sizeof(AUX)); // Initiem auxiliara
            mult(M, C, AUX); // Inmultim solutia M cu matricea C.
            memcpy(M, AUX, sizeof(AUX)); // Copiem rezultatul dat in matricea solutie M.
        }

        memset(AUX, 0, sizeof(AUX)); // Initiem auxiliara
        mult(C, C, AUX); // Ridicam matricea MAT existenta la puterea 2
        memcpy(C, AUX, sizeof(AUX)); // Copiem rezultatul dat in matricea C
    }
}
int main() {
    if (freopen("kfib.in", "r", stdin)) ;
    if (freopen("kfib.out", "w", stdout)) ;

    if (scanf("%d", &n)) ;
    MAT[0][0] = 0;
    MAT[0][1] = MAT[1][0] = MAT[1][1] = 1;

    power (n-1, SOL);

    printf ("%d", SOL[1][1]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}