#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 MultiplyDifferentMatrices(int a[1][2], int b[2][2]){
  long long aux[1][2];

  for(int i=0;i<1;++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 j = 0; j < 2; ++j)
        a[0][j]=aux[0][j];
}
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[1][2]={{0,1}};

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


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