#include <cstdio>

using namespace std;

const int mod=666013;

int d[2][2];
int b[2][2];
int c[2][2];
int rez[2][2];
int k;

void inm_matrici(int a[2][2],int b[2][2],int rez[2][2])
{
    int aux[2][2];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        {
            aux[i][j]=0;
            for(int k=0;k<2;k++)
                aux[i][j]=(aux[i][j]+1LL*a[i][k]*b[k][j])%mod;
        }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++) rez[i][j]=aux[i][j];
}

void rid_put(int a[2][2],int n,int rez[2][2])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++) rez[i][j]=i==j;
    for(int i=1;i<=n;i<<=1)
    {
        if(n&i) inm_matrici(rez,a,rez);
        inm_matrici(a,a,a);
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&k);
    d[0][0]=0;d[0][1]=1;
    b[0][0]=0;b[0][1]=1;b[1][0]=1;b[1][1]=1;
    rid_put(b,k-1,c);
    inm_matrici(d,c,rez);
    printf("%d",rez[0][1]);
    return 0;
}