#define MOD 666013
#define DIM 2
#include <stdio.h>
#include <stdlib.h>

int mx[DIM][DIM], sol[DIM][DIM];

void m_mult(int a[DIM][DIM], int b[DIM][DIM], int c[DIM][DIM]){
    int i, j, k;
    for(i=0; i<DIM; i++) {
        for(j=0; j<DIM; j++) {
            c[i][j] = 0;
            for(k=0; k<DIM; k++)
                c[i][j] = (c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
        }
    }
}

void m_copy(int d[DIM][DIM], int s[DIM][DIM]){
    int i, j;
    for(i=0; i<DIM; i++)
        for(j=0; j<DIM; j++)
            d[i][j]=s[i][j];
}

void invert(int matrix[DIM][DIM]){
    int i, j;
    for(i=0; i<DIM; ++i){
        for(j=0; j<DIM; ++j)
            matrix[i][j]=0;
        matrix[i][i]=1;
    }
}

inline void m_pow(int n, int exp, int matrix[DIM][DIM], int result[DIM][DIM]){
    int aux[DIM][DIM];
    invert(result);
    while(exp){
        if(exp&1){
            m_mult(matrix, result, aux);
            m_copy(result, aux);
        }
        m_mult(matrix, matrix, aux);
        m_copy(matrix, aux);
        exp>>=1;
    }
}

int main(void) {
    FILE *fi = fopen("kfib.in", "r");
    FILE *fo = fopen("kfib.out", "w");
    int n;

    mx[0][0] = 1;
    mx[0][1] = 1;
    mx[1][0] = 1;
    mx[1][1] = 0;

    fscanf(fi, "%d", &n);
    m_pow(DIM, n-1, mx, sol);

    fprintf(fo, "%d\n", sol[0][0]);
    fclose(fi);
    fclose(fo);
    return 0;
}
///Shameless