#include<stdio.h>
int f[3][3],a[3][3],N;
inline void mult (int a[3][3],int b[3][3],int x,int y,int z)
{
    int d[3][3];
    for(int i=1;i<=x;++i)
        for(int j=1;j<=z;++j)
        {
            d[i][j]=0;
            for(int k=1;k<=y;++k)
                d[i][j]=(d[i][j]+(1LL*a[i][k]*b[k][j])%666013)%666013;
        }
    for(int i=1;i<=x;++i)
        for(int j=1;j<=z;++j)
            a[i][j]=d[i][j];
}
void fib(int k)
{
    if(k==1)
        return;
    if(k%2==0)
    {
        fib(k/2);
        mult(a,a,2,2,2);
    }
    else
    {
        fib(k/2);
        mult(a,a,2,2,2);
        mult(a,f,2,2,2);
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    f[1][1]=0;
    f[1][2]=1;
    f[2][1]=1;
    f[2][2]=1;
    a[1][1]=0;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    scanf("%d",&N);
    if(N==0)
        printf(0);
    else
    {
        fib(N);
        printf("%d",a[1][2]);
    }
    return 0;
}