#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 666013
class matrice
{
public:
    int mat[2][2];
    matrice()
    {
        memset(mat,0,sizeof(mat));
    }
    void operator *= (const matrice&b)
    {
        matrice c;
        int i,j,k;
        for(i=0; i<=1; ++i)
            for(j=0; j<=1; ++j)
                for(k=0; k<=1; ++k)
                    c.mat[i][j]=(c.mat[i][j]+(1LL*mat[i][k]*b.mat[k][j])%MOD)%MOD;
        *this=c;
    }
};
    matrice pow(matrice a,int b)
    {
        matrice p;
        p.mat[0][0]=p.mat[1][1]=1;
        for( ; b; b>>=1)
        {
            if (b&1)
                p*=a;
            a*=a;
        }
        return p;
    }
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    matrice a;
    a.mat[0][0]=a.mat[1][0]=a.mat[0][1]=1;
    int k;
    scanf("%d",&k);
    a=pow(a,k-1);
    printf("%d\n",a.mat[0][0]);
    return 0;
}