#include <stdio.h>
#include <string.h>
 
#define mod 666013
 
int nrElem,i;
int matrice1[3][3], matrice2[3][3];
 
inline void inmultire(int a[][3], int b[][3], int c[][3]) 
{
	for (unsigned i = 0; i < 2; i++)
        for (unsigned j = 0; j < 2; j++)
            for (unsigned k = 0; k < 2; k++) 
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
             
}
 
inline void putere(int putere, int matrice[][3]) 
{
    int a[3][3], aux[3][3], i;  
     
    memcpy(a, matrice1, sizeof(matrice1));
    matrice[0][0] = matrice[1][1] = 1;
 
    for (i = 0; (1 << i) <= putere; i++)
    {
        if (putere & (1 << i)) 
        {
            memset(aux, 0, sizeof(aux));
            inmultire(matrice,a, aux);
            memcpy(matrice, aux, sizeof(aux));
        }
 
        memset(aux, 0, sizeof(aux));
        inmultire(a, a, aux);
        memcpy(a, aux, sizeof(a));
    }
}
 
int main() 
{
    FILE *f = fopen ("kfib.in","r");
    FILE *g = fopen ("kfib.out","w");
    fscanf (f,"%d", &nrElem);
    fclose(f);
     
    matrice1[0][0] = 0; 
    matrice1[0][1] = 1; 
    matrice1[1][0] = 1; 
    matrice1[1][1] = 1;
 
    putere(nrElem - 1, matrice2);
 
    fprintf (g,"%d\n", matrice2[1][1]);
    fclose(g);
    return 0;
}