#include<stdio.h>
#define MOD 666013
int a[10][10];
int sol[10][10],N;
void inmu(int a[][10],int b[][10])
{

    int c[10][10];
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j)
            c[i][j]=0;
    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]+1LL*a[i][k]*b[k][j])%MOD;
            }
        for(int i=1;i<=2;++i)
            for(int j=1;j<=2;++j)
            {
                a[i][j]=c[i][j]%MOD;
            }
}
void power()
{
sol[1][1]=1;
sol[2][2]=1;

    for(int i=0;(1<<i)<=N;++i)
    {
        if((1<<i)&N)
        {
        inmu(sol,a);
        }
        inmu(a,a);
    }



}
void afis(int a[][10])
{
    printf("%d\n",sol[1][2]);
}
int main()
{
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%d",&N);

a[1][2]=1;
a[2][1]=1;
a[2][2]=1;
    power();

afis(sol);


}