#include <cstdio>

using namespace std;
int f[3];
int aux[4][4];
int aux2[4][4];
int aux3[4][4];
int mod=666013;
void copy1()
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
          aux2[i][j]=aux[i][j];
}
void m1()
{
    aux3[1][1]=(1LL*aux[1][1]*aux[1][1])%mod+(1LL*aux[1][2]*aux[2][1])%mod;
    aux3[1][2]=(1LL*aux[1][1]*aux[1][2])%mod+(1LL*aux[1][2]*aux[2][2])%mod;
    aux3[2][1]=(1LL*aux[2][1]*aux[1][1])%mod+(1LL*aux[2][2]*aux[2][1])%mod;
    aux3[2][2]=(1LL*aux[2][1]*aux[1][2])%mod+(1LL*aux[2][2]*aux[2][2])%mod;
    aux[1][1]=aux3[1][1]%mod;aux[1][2]=aux3[1][2]%mod;aux[2][1]=aux3[2][1]%mod;aux[2][2]=aux3[2][2]%mod;
}
void m2()
{
    aux3[1][1]=(1LL*aux2[1][1]*aux[1][1])%mod+(1LL*aux2[1][2]*aux[2][1])%mod;
    aux3[1][2]=(1LL*aux2[1][1]*aux[1][2])%mod+(1LL*aux2[1][2]*aux[2][2])%mod;
    aux3[2][1]=(1LL*aux2[2][1]*aux[1][1])%mod+(1LL*aux2[2][2]*aux[2][1])%mod;
    aux3[2][2]=(1LL*aux2[2][1]*aux[1][2])%mod+(1LL*aux2[2][2]*aux[2][2])%mod;
    aux2[1][1]=aux3[1][1]%mod;aux2[1][2]=aux3[1][2]%mod;aux2[2][1]=aux3[2][1]%mod;aux2[2][2]=aux3[2][2]%mod;
}
void lgp(int k)
{
    while(k)
    {
        if(k%2==1)
          {
              if(aux2[2][2]==0)
                copy1();
              else
                m2();
          }
        m1();
        k/=2;
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    scanf("%d",&k);
    //
    aux[1][1]=0;
    aux[2][1]=1;
    aux[1][2]=1;
    aux[2][2]=1;
    k--;
    lgp(k);
    //
    f[1]=1;
    f[2]=1;
    f[1]=(1LL*f[1]*aux2[1][1])%mod+(1LL*f[2]*aux2[2][1])%mod;
    f[2]=(1LL*f[1]*aux2[1][2])%mod+(1LL*f[2]*aux2[2][2])%mod;
    printf("%d",f[1]%mod);
    return 0;
}