#include <cstdio>
#define LL long long
#define mod 666013

using namespace std;

struct matrix{
 LL a,b,c,d;
};
matrix c,unit;
matrix multiply(matrix a,matrix b)
{
    c.a=(a.a*b.a+a.b*b.c)% mod;
    c.b=(a.a*b.b+a.b*b.d)% mod;
    c.c=(a.c*b.a+a.d*b.c)% mod;
    c.d=(a.c*b.b+a.d*b.d)% mod;
    return c;
}
matrix power(matrix a,int exp)
{
    if(exp==0)
        return unit;
    else if(exp==1)
        return a;
    else if(exp%2==0)
    {
        matrix d=power(a,exp/2);
        return multiply(d,d);
    }
    else
    {
        matrix d=power(a,exp/2);
        return multiply(d,multiply(d,a));
    }
}

int main()
{
    int k;
    matrix m,result;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    unit.a=unit.d=1;
    unit.b=unit.c=0;
    m.a=0;
    m.b=m.c=m.d=1;
    if (k!=0)
    {
       result=power(m,k-1);
       printf("%d",result.d%mod);
    }
    else printf("0");
    return 0;
}