#include <cstdio>
#include <cstring>
#define SP 666013


int m[3][3];
int s[3][3];

void ori(int a[3][3],int b[3][3],int c[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c[i][j]=(c[i][j] + (long long)(a[i][k]) *b[k][j] )%SP;
}

void pow(int k) //x*a^b=x*a^1*a^2* etc.
{

    int aux[3][3];
    for(int i=0;(1<<i)<=k;i++)
    {
        if(k&(1<<i))
        {
            //sol=sol*(m^2^i)
            memset(aux,0,sizeof(aux));
            ori(s,m,aux); //aux=s*m
            memcpy(s,aux,sizeof(aux)); //s=aux;
        }

        memset(aux,0,sizeof(aux));
        ori(m,m,aux); // aux=m^2^i * m^2^i = m^(2*2^i)=m^2^(i+1)
        memcpy(m,aux,sizeof(aux)); //m=aux
    }
}


int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    scanf("%d",&k);
    m[1][2]=1;
    m[2][1]=1;
    m[2][2]=1;
    s[1][2]=1;
    if(k==0)
    {
        printf("0");
        return 0;
    }
    pow(k-1);
    //int aux[3][3];
    /*for(int i=1;i<k;i++)
    {
            memset(aux,0,sizeof(aux));
            ori(s,m,aux); //aux=s*m
            memcpy(s,aux,sizeof(aux)); //s=aux;
    }*/

    printf("%d",s[1][2]);
    return 0;
}