#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;

long long v[3][3],sol[3][3],aux[3][3];
int n,p,i,j,q;

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d",&n);
    v[1][2]=v[2][1]=v[2][2]=sol[1][1]=sol[2][2]=1;
    for(p=1;p<=n;p<<=1)
    {
        if(n&p)
        {
            memset(aux,0,sizeof(aux));
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    for(q=1;q<=2;q++)
                        aux[i][q]=(aux[i][q]+sol[i][j]*v[j][q])%mod;
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                for(q=1;q<=2;q++)
                    aux[i][q]=(aux[i][q]+v[i][j]*v[j][q])%mod;
        memcpy(v,aux,sizeof(aux));
    }
    printf("%d",sol[2][1]);
    return 0;
}