// F(n)=M^(n-1) * F(1)  unde matricea const. este (0 1; 1 1)
#include <stdio.h>
#include <stdlib.h>
#define mod 666013

void citire(int *K)
{
    int k;
    FILE *f;
    if((f=fopen("kfib.in", "r"))==NULL)
    {
        fprintf(stderr,"eroare deschidere fisier\n");
        exit(1);
    }
    if(fscanf(f, "%d", &k)!=1)
        exit(1);
    fclose(f);
    *K=k;
}

void afisare(long long int rez)
{
    FILE *g;
    if((g=fopen("kfib.out", "w"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }
    fprintf(g, "%lld", rez);
    fclose(g);
}

void inmultire_matrice(long long A[2][2], long long  B[2][2], long long rez[2][2])
{
    long long temp[2][2];
    temp[0][0]=(A[0][0]*B[0][0]%mod+A[0][1]*B[1][0]%mod)%mod;   
    temp[0][1]=(A[0][0]*B[0][1]%mod+A[0][1]*B[1][1]%mod)%mod;   
    temp[1][0]=(A[1][0]*B[0][0]%mod+A[1][1]*B[1][0]%mod)%mod;   
    temp[1][1]=(A[1][0]*B[0][1]%mod+A[1][1]*B[1][1]%mod)%mod;  
    rez[0][0]=temp[0][0];
    rez[0][1]=temp[0][1];
    rez[1][0]=temp[1][0];
    rez[1][1]=temp[1][1];
}

long long int exp_mat(int K)
{
    if (K==0)
        return 0;
    if (K==1)
        return 1;
    K--;
    long long int rez[2][2], mat[2][2];
    rez[0][0]=1;   rez[0][1]=0;
    rez[1][0]=0;   rez[1][1]=1;
    mat[0][0]=0;   mat[0][1]=1;
    mat[1][0]=1;   mat[1][1]=1;
    // exponentiere rapida
    while (K>0)
    {
        if(K%2==1)
        {
            inmultire_matrice(rez, mat, rez);
        }
        inmultire_matrice(mat, mat, mat);
        K=K/2;
    }
    return rez[1][1];
}

int main()
{
    long long int rez;
    int K;
    citire(&K);
    rez=exp_mat(K);
    afisare(rez);
    return 0;
}