#include<stdio.h>
#include<string.h>
int n,i,a[3][3],s[3][3],c[3][3],x[3][3];
void M(int a[][3],int b[][3],int c[][3])
{
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%666013;

}
int main()
{
    freopen("kfib.in","r",stdin),freopen("kfib.out","w",stdout),scanf("%d",&n),a[0][1]=a[1][0]=a[1][1]=s[0][0]=s[1][1]=1,memcpy(c,a,sizeof(a));
    for(i=0;(1<<i)<n;i++)
    {
        if((n-1)&(1<<i))
            M(s,c,x),memcpy(s,x,sizeof(x));
        M(c,c,x),memcpy(c,x,sizeof(c));
    }
    printf("%d",s[1][1]);
}