#include<cstdio>
#define _MOD 666013
typedef unsigned long long ull;
struct matrix
{
    ull a,b,c,d;
    matrix operator*(matrix Q)
    {
        matrix rez;
        rez.a=(a*Q.a+b*Q.c) %_MOD; rez.c=(a*Q.b+b*Q.d) %_MOD;
        rez.b=(c*Q.a+d*Q.c) %_MOD; rez.d=(c*Q.b+d*Q.d) %_MOD;
        return rez;
    };
};

matrix m_pow(matrix B, int E)
{
    if (E==1)
        return B;
    matrix exp_pe2=m_pow(B,E/2);
    if (E%2==0)
        return exp_pe2*exp_pe2;
    else
        return exp_pe2*exp_pe2*m_pow(B,1);
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int K; scanf("%d",&K);
    matrix Z; Z.a=0;Z.b=1;Z.c=1;Z.d=1;
    printf("%d",m_pow(Z,K-1).d);
    return 0;
}