#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
long long  sol[3][3],n;
void inmultire(long long a[3][3],long long b[3][3], long long 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(long long  sol[3][3],long long n )
{
    long long 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]);
}