#include<fstream>
#define ro 666013
using namespace std;
ifstream fi("kfib.in");
ofstream fo("kfib.out");

long long a[3][3];
long long z[3][3];
long long s[3][3];
int k;

void copiere(long long x[3][3],long long y[3][3]){
     int i,j;
     for(i=1;i<=2;i++)
       for(j=1;j<=2;j++) y[i][j]=x[i][j];
}

void initializare(){
     z[1][1]=0; z[1][2]=1;
     z[2][1]=1; z[2][2]=1;
     
     s[1][1]=1; s[1][2]=0;
     s[2][1]=0; s[2][2]=1;
}

void exp_log(){
     int i,j;
     
     k--;
     initializare();
     
     while(k){
              if(k&1){
                      for(i=1;i<=2;i++)
                      for(j=1;j<=2;j++)
                         a[i][j]=(s[i][1]*z[j][1] + s[i][2]*z[j][2])%ro;
                      
                      copiere(a,s); 
                     }
                                  
              for(i=1;i<=2;i++)
              for(j=1;j<=2;j++)
                 a[i][j]=(z[i][1]*z[j][1] + z[i][2]*z[j][2])%ro;    
                   
              copiere(a,z);    
              
              k>>=1;
             }
    
    fo<<s[2][2];
}

int main(){
    fi>>k;

    if(k<1) fo<<k;
    else exp_log();
    
    fi.close();
    fo.close();
    return 0;
}