#include<stdio.h>
#include<cstring>
#define mod 666013
using namespace std;

int k;
int sol[3][3],add[3][3];

void init()
{
    add[1][2]=add[2][1]=add[2][2]=1;
    sol[1][1]=sol[2][2]=1;
}

void up(int a[3][3],int b[3][3])
{
    int aux[3][3];
    memset(aux,0,sizeof(aux));
    for(int i=1;i<=2;i++)
     for(int j=1;j<=2;j++)
      for(int l=1;l<=2;l++)
       aux[i][j]+=(1LL*a[i][l]*b[l][j])%mod,aux[i][j]%=mod;
    memcpy(a,aux,sizeof(aux));
}

void solve()
{
    k--;
    for(int i=0;(k>>i);i++)
    {
        if( ((k>>i)&1)==1 ) up(sol,add);
        up(add,add);
    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&k);
    init();
    solve();
    if(k+1) printf("%d",sol[2][2]);
    else printf("0");

    fclose(stdin);
    fclose(stdout);
    return 0;
}