#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

#define MOD  666013
int base[2][2]={{0,1},{1,1}};  //or Z

void MultiplyMatrices(int a[2][2], int b[2][2]){
    long long aux[2][2];

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

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


    for (int i = 0; i<2; ++i)
    for (int j = 0; j<2; ++j)
        a[i][j]=aux[i][j];
}
int main() {
  int k;
  fin>>k;

  int solution[2][2]={{1,0}, {0,1}};

  while(k){
        if(k%2==1) {
            MultiplyMatrices(solution,base);
        }
        MultiplyMatrices(base,base);
        k/=2;
    }
        fout<<solution[0][1]<<"\n";


    fout.close();
    fin.close();
    return 0;
}