#include <cstdio>

using namespace std;

const int mod=666013,m=2;
struct matrice
{
    int v[m][m];
    matrice operator *(matrice a)
    {
        matrice b;
        b.nula();
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<m;k++) b.v[i][k]=(b.v[i][k]+1LL*v[i][j]*a.v[j][k])%mod;
        return b;
    }
    void nula()
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++) v[i][j]=0;
    }
    void unitate()
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++) v[i][j]=(i==j);
    }
};

matrice rid_putere(matrice a,int n)
{
    matrice p;
    p.unitate();
    for(int i=1;i<=n;i<<=1)
    {
        if(n&i) p=p*a;
        a=a*a;
    }
    return p;
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    scanf("%d",&k);
    matrice a;
    a.nula();
    a.v[0][0]=0;
    a.v[0][1]=a.v[1][0]=a.v[1][1]=1;
    matrice sol=rid_putere(a,k-1);
    printf("%d",sol.v[1][1]);
    return 0;
}