#include<stdio.h>

#define plm long long
#define b 666013

plm a[2][2]={0,1,1,1},rez[2][2]={1,0,0,1},n;

void mul(plm A[][2],plm B[][2])
{
    int C[2][2]={0,0,0,0};
    
    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] + (A[i][k]*B[k][j]) % b) %b;
                
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            A[i][j]=C[i][j];
}


int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld",&n);
    
    --n;
    
    for(;n; n/=2)
        {
            if (n%2==1)
                mul(rez,a);
            
            mul(a,a);
        }
    
    printf("%lld\n",rez[1][1]);
    
    return 0;
}