#include <iostream>
#include <fstream>
using namespace std;
const int MOD=666013;
long long x[3][3],y[3][3],z[3][3];

void inmultire(long long  a[3][3], long long b[3][3], int n){
  long long aux[3][3];

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      aux[i][j]=0;
      for(int k=1;k<=n;k++){
        aux[i][j]+=a[i][k]*b[k][j];

      }
    }
  }
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) a[i][j]=aux[i][j]%MOD;


}


int main()
{
    long long k;
    ifstream in("kfib.in");
    in>>k;
    x[1][2]=x[2][1]=x[2][2]=1;
    y[1][1]=y[2][2]=1;
    k--;
    while(k>0){

      if(k%2!=0) {
        inmultire(y,x,2);
      }
      k/=2;
      inmultire(x,x,2);

    }
    ofstream out("kfib.out");
    out<<y[2][2];
    return 0;
}