#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int mod=666013;

inline void inm(int a[2][2],int b[2][2])
{
    int i,j,k,c[2][2];
    for(i=0;i<2;i++)
        for(j=0;j<2;++j)
            c[i][j]=0;
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            for(k=0;k<2;++k)
                c[i][j] = (c[i][j] + 1LL*a[i][k]*b[k][j])%mod;
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            a[i][j]=c[i][j];
}

int a[2][2],b[2][2];

inline void solve(int lvl)
{
    while(lvl)
    {
        if(lvl&1)
            inm(a,b);
        inm(b,b);
        lvl>>=1;
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n,i,j;
    scanf("%d",&n);
    int t1=1,t2=1;
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            b[i][j] = (i!=1 || j!=1);
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            a[i][j]= (i==j);
    solve(n-1);
    printf("%d",(a[1][0]*t1 + a[1][1]*t2)%mod);
}