#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MOD 666013

void inmultire(int R[2][2], int A[2][2], int B[2][2])
{
    int AUX[2][2] = {0};
    
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
            {
               AUX[i][j] = (AUX[i][j] + 1LL*A[i][k]*B[k][j])%MOD;
            }
            
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            R[i][j] = AUX[i][j];
}

void calculare_putere(int R[2][2], int Z[2][2], long long n)
 {
    R[0][0] = R[1][1] = 1;
    R[0][1] = R[1][0] = 0;
    
    while(n)
    {
        if(n % 2 == 1)
           inmultire(R, R, Z);
           
        inmultire(Z, Z, Z);
        n /= 2;
    }
}

int main()
{   FILE *input, *output;
    
    if((input = fopen("kfib.in", "r")) == NULL)
    {
        perror("Eroare la deschidere fisier intrare.");
        exit(-1);
    }

    if((output = fopen("kfib.out", "w")) == NULL)
    {
        perror("Eroare la deschidere fisier iesire.");
        exit(-1);
    } 

    long long k;
    int REZ[2][2], Z[2][2];
    
    fscanf(input, "%lld", &k);
    
    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;
    
    calculare_putere(REZ, Z, k);
    
    fprintf(output, "%d\n", REZ[0][1]);

    if(fclose(input) == -1)
    {
        perror("Eroare la inchidere fisier intrare.");
        exit(-1);
    }
    
    if(fclose(output) == -1)
    {
        perror("Eroare la inchidere fisier iesire.");
        exit(-1);
    }
    
    return 0;
}