#include <bits/stdc++.h>
#define mod 666013
using namespace std;

long long n,mat[3][3],sol[3][3],C[3][3],aux[3][3];


inline void inm(long long A[3][3],long long B[3][3],long long C[3][3])
{
    for (int i=0;i<2;++i)
        for (int j=0;j<2;++j)
            for (int k=0;k<2;++k)
                C[i][j]+=(A[i][k]*B[k][j])%mod;

}

void lg_put (long long p)
{
    if (p==1)
        return; ///nu inmultesc nimic
    if (!(p%2))
    {
        lg_put(p/2);
        memcpy(aux,mat,sizeof(mat));
        memset(mat,0,sizeof(mat));
        inm(aux,aux,mat); ///inmultim matricele deja ridicate la putere
        return;
    }
    lg_put(p/2);

    memcpy(aux,mat,sizeof(mat));
    memset(mat,0,sizeof(mat));
    inm(aux,aux,mat);

    memcpy(aux,mat,sizeof(mat));
    memset(mat,0,sizeof(mat));
    inm(aux,sol,mat);
}


int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    mat[0][1]=mat[1][0]=mat[1][1]=1;
    sol[0][1]=sol[1][0]=sol[1][1]=1;
    lg_put(n);
    printf("%lld ",mat[1][0]);


    return 0;
}