#include<cstdio>
#define m 666013
using namespace std;
long long z[3][3],mi[3][3],a[3][3];
int k;
void matp(int k)
{ for (;k;k>>=1)
    {if ( k&1 ) //sol= (sol * a) % m;
        {mi[1][1]=((a[1][1]*z[1][1])%m+ (a[1][2]*z[2][1])%m)%m;
         mi[1][2]=((a[1][1]*z[1][2])%m+ (a[1][2]*z[2][2])%m)%m;
         mi[2][1]=((a[2][1]*z[1][1])%m+ (a[2][2]*z[2][1])%m)%m;
         mi[2][2]=((a[2][1]*z[1][2])%m+ (a[2][2]*z[2][2])%m)%m;
         a[1][1]=mi[1][1]; a[2][1]=mi[2][1]; a[1][2]=mi[1][2]; a[2][2]=mi[2][2];
        }
     mi[1][1]=((z[1][1]*z[1][1])%m + (z[1][2]*z[2][1])%m)%m;
     mi[1][2]=((z[1][1]*z[1][2])%m + (z[1][2]*z[2][2])%m)%m;
     mi[2][1]=((z[2][1]*z[1][1])%m + (z[2][2]*z[2][1])%m)%m;
     mi[2][2]=((z[2][1]*z[1][2])%m + (z[2][2]*z[2][2])%m)%m;
    // a=(a * a) % m;
     z[1][1]=mi[1][1]; z[2][1]=mi[2][1]; z[1][2]=mi[1][2]; z[2][2]=mi[2][2];
    }
}
int main()
{freopen("kfib.in","rt",stdin);
 freopen("kfib.out","wt",stdout);
 scanf("%d",&k);
 z[1][2]=z[2][1]=z[2][2]=1;
 a[1][2]=a[2][1]=a[2][2]=1;
 matp(k-2);
 printf("%lld\n",a[2][2]);
 return 0;
}