#include <fstream>
#define p 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void Putere(int &a,int &b,int &c,int &d,int k)
    {int a1,b1,c1,d1;
    a1=a;b1=b;c1=c;d1=d;
    if(k>1){
     if(k%2==1){int a2,b2,c2,d2;
                a2=a;b2=b;c2=c;d2=d;
                Putere(a1,b1,c1,d1,k-1);
                a=(1LL*a1*a2%p+1LL*b1*c2%p)%p;
                b=(1LL*a1*b2%p+1LL*b1*d2%p)%p;
                c=(1LL*c1*a2%p+1LL*d1*c2%p)%p;
                d=(1LL*b1*c2%p+1LL*d1*d2%p)%p;
               }
     if(k%2==0){a=(1LL*a1*a1%p+1LL*b1*c1%p)%p;
                b=(1LL*a1*b1%p+1LL*b1*d1%p)%p;
                c=(1LL*c1*a1%p+1LL*d1*c1%p)%p;
                d=(1LL*b1*c1%p+1LL*d1*d1%p)%p;
                Putere(a,b,c,d,k/2);
               }
        }
    }
int main()
{int k,a,b,c,d;
 fin>>k;
 a=0;b=c=d=1;
 Putere(a,b,c,d,k-1);
 fout<<d;
}