#include <cstdio>
#include <algorithm>
using namespace std;
#define MOD 666013

long long F[2][2]={{0,1},{1,1}}; //here will be answer
long long A[2][2]={{0,1},{1,1}};
long long r[2][2];
int n;

void pow(int n)
{
    if(n>1)
    {
        pow(n/2);
        for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)r[i][j]=F[i][j];
        F[0][0]=(r[0][0]*r[0][0]+r[0][1]*r[1][0])%MOD;
        F[0][1]=(r[0][0]*r[0][1]+r[0][1]*r[1][1])%MOD;
        F[1][0]=(r[1][0]*r[0][0]+r[1][1]*r[1][0])%MOD;
        F[1][1]=(r[1][0]*r[0][1]+r[1][1]*r[1][1])%MOD;
        if(n%2==1)
        {
            for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)r[i][j]=F[i][j];
            F[0][0]=(r[0][0]*A[0][0]+r[0][1]*A[1][0])%MOD;
            F[0][1]=(r[0][0]*A[0][1]+r[0][1]*A[1][1])%MOD;
            F[1][0]=(r[1][0]*A[0][0]+r[1][1]*A[1][0])%MOD;
            F[1][1]=(r[1][0]*A[0][1]+r[1][1]*A[1][1])%MOD;
        }
    }
}

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

    scanf("%d",&n);
    pow(n+1);

    printf("%lld\n",F[0][0]);
  /*  for(int i=0;i<2;i++)
    {

        for(int j=0;j<2;j++)printf("%d ",F[i][j]); printf("\n");
    }*/

    return 0;
}