#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
int sol[3][3],n;
void inmultire(int a[3][3],int b[3][3], int c[3][3])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
        c[i][j]=(c[i][j]+((a[i][k]%mod)*b[k][j]%mod)%mod)%mod;
}
void lg_putere(int sol[3][3],int n )
{
    int m[3][3],aux[3][3];
    memset(m,0,sizeof(m));
    m[1][0]=1;
    m[0][1]=1;
    m[1][1]=1;
    for(int i=0;(1<<i)<=n;i++)
    {
        if((1<<i)&n)
        {
            memset(aux,0,sizeof(aux));
            inmultire(sol,m,aux);
            memcpy(sol,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        inmultire(m,m,aux);
        memcpy(m,aux,sizeof(m));
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%lld",&n);
    sol[0][0]=1;
    sol[0][1]=1;
    lg_putere(sol,n-1);
    printf("%ld",sol[0][0]);
}