#include <iostream>
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

#define MOD 666013

int k;
int rez[3][3], I[3][3];

void citeste(){

    f >> k;

}

void inmult(int a[3][3], int b[3][3]){

    int aux[4][4];

    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++) aux[i][j] = 0;

    for(int i=1; i<=2; i++){
        for(int j=1; j<=2; j++){
            for(int k=1; k<=2; k++){
                aux[i][j] += ( 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }

    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++) a[i][j] = aux[i][j];

}

void putere(){

    int p = k;

    //initializez rezultatul
    rez[1][1] = 1;
    rez[1][2] = 0;
    rez[2][1] = 0;
    rez[2][2] = 1;

    while(p){
        if ( p % 2 == 1){
            inmult(rez, I);
        }
        inmult(I,I);
        p = p /2;
    }

}

void rezolva(){

    //aflu matricea constanta astfel :
    // terminii din care se obtine al ilea termen : adica ultimii 2
    // (0,1) * (x x) = (1,2) => X = 0 1
  //           (x x)                1 1

    //ridic matricea la k-2 pentru a obtine al-klea termen
    I[1][1] = 0;
    I[1][2] = 1;
    I[2][1] = 1;
    I[2][2] = 1;

    putere();

    g << rez[2][1] % MOD << "\n";

}

int main(){

    citeste();
    rezolva();

}