#include <cstdio>
#include <cstring>

using namespace std;

const int MOD=666013;

class matrice
{
public:
    long long mat[2][2];
    matrice()
    {
        memset(mat,0,sizeof(mat));
    }
    void init()
    {
        mat[0][0]=mat[1][0]=mat[0][1]=1;
    }
    void operator*=(const matrice &other)
    {
        int i,j,k;
        matrice c;
        for(i=0; i<2; i++)
            for(j=0; j<2; j++)
                for(k=0; k<2; k++)
                    c.mat[i][j]=(c.mat[i][j]+(mat[i][k]*other.mat[k][j]*1LL)%MOD)%MOD;
        *this=c;
    }
};

int pow(int b)
{
    matrice a,rez;
    a.init();
    rez.mat[0][0]=rez.mat[1][1]=1;
    for(; b; b>>=1)
    {
        if(b&1)
            rez*=a;
        a*=a;
    }
    return rez.mat[0][0];
}

int main()
{
    int n;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    printf("%d",pow(n-1));
    return 0;
}