#include <stdio.h>
#include <cstring>
#define mod 666013

using namespace std;

int n,z[3][3],sol[3][3];

inline void mult(int a[][3],int b[][3],int c[][3])
{
    for(int i=1;i<=2;i++)
      for(int j=1;j<=2;j++)
        for(int k=1;k<=2;k++)
        c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
}
void log_power(int p,int sol[][3])
{
    int c[3][3],aux[3][3];
    sol[1][1]=sol[2][2]=1;

    memcpy(c,z,sizeof(z));
    for(int i=0;(1<<i)<=p;i++)
    {
        if((1<<i)&p)
        {
            memset(aux,0,sizeof(aux));
            mult(sol,c,aux);
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        mult(c,c,aux);
        memcpy(c,aux,sizeof(aux));
    }
}


int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    z[1][1]=0;z[1][2]=1;
    z[2][1]=1;z[2][2]=1;
    scanf("%d",&n);

    log_power(n-1,sol);

    printf("%d",sol[2][2]);
}