#include <cstdio>

const int impartitor=666013;
int n,a[3][3],b[3][3];

void produs(int a[3][3], int b[3][3], int c[3][3])
{
    int i,j,k;
    for (i=1; i<=2; i++)
        for (j=1; j<=2; j++)
    {
        c[i][j]=0;
        for (k=1; k<=2; k++)
            c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%impartitor)%impartitor;
    }
}

void copiaza(int a[3][3], int t[3][3])
{
    int i,j;
    for (i=1; i<=2; i++)
        for (j=1; j<=2; j++)
        a[i][j]=t[i][j];
}

void ridicare(int a[3][3], int n, int b[3][3])
{
    if (n==0)
    {
        b[1][1]=1; b[1][2]=0;
        b[2][1]=0; b[2][2]=1;
    }
    else
        if (n==1) copiaza(b,a);
        else
        {
            int t[3][3];
            ridicare(a,n/2,t);
            produs(t,t,b);
            if (n%2==1)
            {
                produs(b,a,t);
                copiaza(b,t);
            }
        }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    a[1][1]=1; a[1][2]=1;
    a[2][1]=1; a[2][2]=0;
    ridicare(a,n-2,b);
    printf("%d\n",(b[1][1]+b[2][1])%impartitor);
    return 0;
}