#include <fstream>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
long long a[3][3],rez[3][3],MOD=666013,n,x,y,z,t,x2,y2,z2,t2;
void lg(long long n)
{
    while (n)
    {
        if (n%2==0) {x=a[1][1]; y=a[1][2]; z=a[2][1]; t=a[2][2]; a[1][1]=(x*x+y*z)%MOD; a[1][2]=(x*y+y*t)%MOD; a[2][1]=(x*z+z*t)%MOD; a[2][2]=(y*z+t*t)%MOD; n/=2;}
        else {n--; x=a[1][1]; y=a[1][2]; z=a[2][1]; t=a[2][2]; x2=rez[1][1]; y2=rez[1][2]; z2=rez[2][1]; t2=rez[2][2]; rez[1][1]=(x2*x+y2*z)%MOD; rez[1][2]=(x2*y+y2*t)%MOD; rez[2][1]=(z2*x+t2*z)%MOD; rez[2][2]=(z2*y+t2*t)%MOD;}
    }
}
int main()
{
    in>>n;
    if (n==0) {out<<0; return 0;}
    if (n==1) {out<<1; return 0;}
    if (n==2) {out<<1; return 0;}
    a[1][2]=a[2][1]=a[2][2]=1;
    rez[1][1]=rez[2][2]=1;
    lg(n);
    out<<rez[1][2];

}