#include<cstdio>
#define mod 666013
long long rez[3][3],a[3][3],ca[3][3];
int main ()
{freopen ("kfib.in","r",stdin);
freopen ("kfib.out","w",stdout);
long long n,i,j;
scanf("%lld",&n);
rez[1][1]=rez[2][2]=1;
a[1][2]=a[2][1]=a[2][2]=1;
n-=2;
while(n)
    {if(n%2==1)
        {n--;
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                ca[i][j]=rez[i][j];
        rez[1][1]=((ca[1][1]*a[1][1])%mod+(ca[1][2]*a[2][1]))%mod;
        rez[1][2]=((ca[1][1]*a[1][2])%mod+(ca[1][2]*a[2][2]))%mod;
        rez[2][1]=((ca[2][1]*a[1][1])%mod+(ca[2][2]*a[2][1]))%mod;
        rez[2][2]=((ca[2][1]*a[1][2])%mod+(ca[2][2]*a[2][2]))%mod;
        }
    else
        {n/=2;
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                ca[i][j]=a[i][j];
        a[1][1]=((ca[1][1]*ca[1][1])%mod+(ca[1][2]*ca[2][1]))%mod;
        a[1][2]=((ca[1][1]*ca[1][2])%mod+(ca[1][2]*ca[2][2]))%mod;
        a[2][1]=((ca[2][1]*ca[1][1])%mod+(ca[2][2]*ca[2][1]))%mod;
        a[2][2]=((ca[2][1]*ca[1][2])%mod+(ca[2][2]*ca[2][2]))%mod;
        }
    }
printf("%lld",(rez[1][2]+rez[2][2])%mod);
return 0;
}