#include <cstdio>
#define MOD 666013

using namespace std;

int a[3][3],b[3][3];

inline void Mult(int a[][3], int b[][3])
{
    int i,j,k,sol[3][3];
    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j) sol[i][j]=0;
    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j)
            for(k=1;k<=2;++k)
                sol[i][j]=(1LL*sol[i][j]+1LL*a[i][k]*b[k][j])%MOD;
    for(i=1;i<=2;++i)
        for(j=1;j<=2;++j) a[i][j]=sol[i][j];
}

inline void Pow_Log(int p)
{
    int sol[3][3];
    sol[1][1]=sol[2][2]=1; sol[1][2]=sol[2][1]=0;
    while(p)
    {
        if(p&1)
        {
            Mult(sol,b);
            --p;
        }
        p>>=1;
        Mult(b,b);
    }
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j) b[i][j]=sol[i][j];
}

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