#include<bits/stdc++.h>

using namespace std;
// Ugly numbers 2 3 5
/*
unsigned ugly(long long f)
{
    long long *uglyno;
    uglyno=new long long[f+1];
    uglyno[0]=1;
    long long ug2=2;
    long long ug3=3;
    long long ug5=5;
    long long i2=0,i3=0,i5=0;
    for(long long i=1;i<f;i++)
    {
        long long ugf=min(ug2,min(ug3,ug5));
        uglyno[i]=ugf;
        if(ug2==ugf)
        {
           i2++;
           ug2=uglyno[i2]*2;
        }
        if(ug3==ugf)
        {
           i3++;
           ug3=uglyno[i3]*3;
        }
        if(ug5==ugf)
        {
           i5++;
           ug5=uglyno[i5]*5;
        }
    }
    return uglyno[f-1];
}
int main()
{
   cout<<ugly(4);
   return 0;
}*/
// Al n-lea termen al lui fibonacci
// 1   Fn = {[(√5 + 1)/2] ^ n} / √5
/*long long fib(long long n)
{
     double phi=(1+sqrt(5))/2;
     return round((pow(phi,n))/sqrt(5));
}
int main()
{
   long long n=;
   cout<<fib(n);
}*/
/*( 1 1 ) ^ n      =(  Fn+1  Fn  )
( 1 0 )           (  Fn    Fn-1 )*/
#define mod 666013
ifstream in("kfib.in");
ofstream out("kfib.out");
long long M[2][2]={{1,1},{1,0}};
void multiply(long long F[2][2],long long M[2][2]);
void power(long long F[2][2],long long n);
long long fib(long long n)
{
    long long F[2][2]= {{1,1},{1,0}};
    if(n==0)
        return 0;
    power(F,n-1);
    return F[0][0];
}
void power(long long F[2][2],long long n)
{
    if(n==0 || n==1)
        return ;
    power(F,n/2);
    multiply(F,F);
    if(n%2==1)
        multiply(F,M);
}
void multiply(long long F[2][2],long long M[2][2])
{
    long long x =  F[0][0]*M[0][0]%mod + F[0][1]*M[1][0]%mod;
    long long y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]%mod;
    long long z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]%mod;
    long long w =  F[1][0]*M[0][1]%mod + F[1][1]*M[1][1]%mod;

    F[0][0] = x%mod;
    F[0][1] = y%mod;
    F[1][0] = z%mod;
    F[1][1] = w%mod;
}
int main()
{
  long long n = 9;
  in>>n;
  out<<fib(n);
  return 0;
}