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

#define mod 666013

int64_t A[2][2] = { {0 , 1} , {1 , 1} };
int64_t C[2][2] = {  { 0 ,1 } , { 1 , 1 } };

int64_t puterelog(int64_t A[2][2] , int exp){

      for( int i = 1 ; i <= exp ; i = (i<<1) ){

            if( i & exp ){
                inmultire( A , C);
            }
            inmultire(A , A);
      }
}

void inmultire( int64_t A[2][2] , int64_t B[2][2]){

      C[0][0] = ( A[0][0] * B[0][0] +  A[0][1] * B[1][0] ) % mod;
      C[0][1] = ( A[0][0] * B[0][1] +  A[0][1] * B[1][1] ) % mod;
      C[1][0] = ( A[1][0] * B[0][0] +  A[1][1] * B[1][0] ) % mod;
      C[1][1] = ( A[1][0] * B[0][1] +  A[1][1] * B[1][1] ) % mod;
}


int main(){

    FILE * input , * output ;

    input = fopen( "kfib.in" , "r");
    if(!input){

          perror("nu-i bun ");
          return 0;
    }

    output = fopen ( "kfib.out" , "w ");
    if(!output){

          perror("nu-i bun ");
          return 0;
    }

    int64_t k ;
    fscanf( input , "%d" , &k );

    puterelog( A , k - 1);
    fprintf(output , "%lli" , C[0][0] + C[0][1] );

  return 0;
}