#include<stdio.h>
using namespace std;

const int MOD=666013;
const int MAX=3;
int m,p,a[MAX][MAX],c[MAX][MAX],n[MAX][MAX],i,k;

int in[3][3];


void inmultire(int a[][MAX],int b[][MAX],int c[][MAX],int m,int p,int q)
{
    int tmp[MAX][MAX];

    int s1,k,i,j;
    for (i=1;i<=m;i++)
        {
            for (j=1;j<=q;j++)
                {
                    s1=0;

                    for (k=1;k<=p;k++)
                        s1=(s1+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
                    tmp[i][j]=s1;
                }
        }


    for (i=1;i<=m;i++)
        for (j=1;j<=q;j++)
            c[i][j]=tmp[i][j];
}

void putere (int a[][MAX],int p,int m,int put)
{
    int i,j;
    if (put==0)
    {
        for (i=1;i<=p;i++)
            for (j=1;j<=m;j++)
                a[i][j]=in[i][j];
    }
    else
        if (put%2==0)
        {
            inmultire (a,a,a,2,2,2);
            putere (a,2,2,put/2);
        }
        else
        {
            int rez[MAX][MAX];
              for (i=1;i<=p;i++)
                 for (j=1;j<=m;j++)
                    rez[i][j]=a[i][j];
              putere (a,2,2,put-1);
              inmultire (a,rez,a,2,2,2);
        }

}

int main()
{
   freopen("kfib.in","r",stdin);
   freopen("kfib.out","w",stdout);

   scanf("%d",&k);

   if (k==0 || k==1) printf("1 ");
   else

  {
    n[1][1]=1;
    n[1][2]=1;
    in[1][1]=in[2][2]=1;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;

putere(a,2,2,k-2);

inmultire(n,a,c,1,2,2);

    printf("%d",c[1][2]%666013);

  }
    return 0;
}