#include<stdio.h>
#include<string.h>
#define mod 666013
int n,i,a[2][2],ans[2][2];
inline void f(int a[2][2], int b[2][2], int rez[2][2])
{
    int i,j,k;
    rez[0][0]=rez[0][1]=rez[1][0]=rez[1][1]=0;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            for(k=0;k<=1;k++)
                rez[i][j]=(rez[i][j]+1LL*a[i][k]*b[k][j])%mod;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            a[i][j]=rez[i][j];
}
inline void power(int m,int mat[2][2])
{
    int c[2][2],aux[2][2];
    memcpy(c,a,sizeof(a));
    mat[0][0]=mat[1][1]=1;
    for(;m;m>>=1)
    {
        if(m&1)
            f(mat,c,aux);
        f(c,c,aux);
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    a[0][0]=0;a[0][1]=1;
    a[1][0]=1;a[1][1]=1;
    power(n-1,ans);
    printf("%d\n",ans[1][1]);
    return 0;
}