#include <iostream>
#include <fstream>
#include <string.h>
#define N 2
#define mod 666013
#define LL long long
#define FIN "kfib.in"
#define FOUT "kfib.out"

using namespace std;

void mult(LL A[ 3 ][ 3 ], LL B[ 3 ][ 3 ]) {

     int i,

         j,

         z;

     LL C[ 3 ][ 3 ];

     memset(C, 0, sizeof( C ));

     for(i = 1; i <= N; i++)

         for(j = 1; j <= N; j++) {

             for(z = 1; z <= N; z++)
 
                 C[ i ][ j ] = (C[ i ][ j ] + A[ i ][ z ] * B[ z ][ j ] % mod ) % mod;
         }
    
     memcpy(A, C, sizeof(C));
};

void readAndsolve() {

    int i;

    LL k;

    ifstream I(FIN); 
    ofstream O(FOUT);

    I>>k;

    LL A[3][3]; 
    LL B[3][3];
      
    A[1][1] = 1; A[1][2] = 0; 
    A[2][1] = 0; A[2][2] = 1;

    B[1][1] = 0; B[1][2] = 1; 
    B[2][1] = 1; B[2][2] = 1;

    for(i = 0; ((1<<i) <= k); i++) {

          if( k & (1<<i) ) mult(A, B);

          mult(B, B); 
    }

    O<<A[2][1];
}

//1,1,2,3,5,8,13,21,33,...

int main() {

    readAndsolve();

    return(0);
}