#include<cstdio>
using namespace std;
#define mod 666013
struct MTRX {long long a[2][2];} F,U;
void pdt(MTRX A, MTRX B, MTRX &C)
{
    C.a[0][0]=((A.a[0][0]*B.a[0][0])%mod+(A.a[0][1]*B.a[1][0])%mod)%mod;
    C.a[0][1]=((A.a[0][0]*B.a[0][1])%mod+(A.a[0][1]*B.a[1][1])%mod)%mod;
    C.a[1][0]=((A.a[1][0]*B.a[0][0])%mod+(A.a[1][1]*B.a[1][0])%mod)%mod;
    C.a[1][1]=((A.a[1][0]*B.a[0][1])%mod+(A.a[1][1]*B.a[1][1])%mod)%mod;
}
void calcul(MTRX &S, MTRX &T, int k)
{
    if (k>1)
    {
        if (k%2)
            {
                calcul(S,T,k-1);
                pdt(S,T,S);
            }
        else
            {
                calcul(S,T,k/2);
                pdt(S,S,S);
            }
    }
}
int n;
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    U.a[0][0]=U.a[0][1]=U.a[1][0]=1;
    F=U;
    calcul(F,U,n);
    printf("%d\n",F.a[0][1]%mod);
    return 0;
}