#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n,mod=666013;
long long a11,a12,a21,a22;
void expmat(int n,long long &a11,long long &a12,long long &a21,long long &a22){
    long long b11,b12,b21,b22;
    if (n==1){
        a11=1;a21=1;
        a12=1;a22=0;
        return;
    }
      else
        if (n%2==0){
           expmat(n/2,b11,b12,b21,b22);
           b11=b11%mod;b21=b21%mod;b12=b12%mod;b22=b22%mod;
           a11=((b11*b11)%mod+(b12*b21)%mod)%mod;
           a12=((b11*b12)%mod+(b12*b22)%mod)%mod;
           a21=((b11*b21)%mod+(b22*b21)%mod)%mod;
           a22=((b21*b12)%mod+(b22*b22)%mod)%mod;
        }
          else{
             expmat(n-1,b11,b12,b21,b22);
             a11=(b11%mod+b12%mod)%mod;
             a12=b11%mod;
             a21=(b21%mod+b22%mod)%mod;
             a22=b21%mod;
          }
}
int main(){
   fin>>n;
   fin.close();
   expmat(n-1,a11,a12,a21,a22);
   fout<<a11;
   fout.close();
   return 0;
}