#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
void prod(int a[10][10],int b[10][10],int c[10][10])
{
     c[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%666013;
     c[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%666013;
     c[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%666013;
     c[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%666013;
}
void power(int k,int z[10][10],int sol[10][10])
{
    if(k>1)
      if(k%2)
       {
           int aux[10][10];
           power(k-1,z,aux);
           prod(z,aux,sol);
       }
       else
       {
            int aux[10][10];
            power(k/2,z,aux);
            prod(aux,aux,sol);
       }
       else {
        for(int i=1;i<=2;++i)
            for(int j=1;j<=2;++j)
               sol[i][j]=z[i][j];
       }
}
int main()
{
    int k;
    int a[10][10],z[10][10];
    z[1][1]=0;
    z[1][2]=1;
    z[2][1]=1;
    z[2][2]=1;
    f>>k;
    power(k-1,z,a);
    g<<a[2][2];
    return 0;
}