#include<cstdio>
#define nr 666013
using namespace std;
long long a[3][3],b[3][3],i,j,n;
long long p(long x,long y)
{
    long long m=(((x*(y/1000))%nr)*1000)%nr+(x*(y%1000))%nr;
        return m%nr;
}
void patrat()
{
    long x[3][3],i,j;
    x[1][1]=p(a[1][1],a[1][1])+p(a[2][1],a[1][2]);
    x[1][2]=p(a[1][2],(a[1][1]+a[2][2])%nr);
    x[2][1]=p(a[2][1],(a[1][1]+a[2][2])%nr);
    x[2][2]=p(a[1][2],a[2][1])+p(a[2][2],a[2][2]);
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j]%nr;
}
void echilibrare()
{
  
    if(a[1][2]<0&&a[2][1]>0)
        a[1][2]=a[2][1];
    if(a[2][1]<0&&a[1][2]>0)
    a[2][1]==a[1][2];
    if(a[1][1]<0&&a[1][2]>0&&a[2][2]>0)
    a[1][1]=a[2][2]-a[1][2];
    if(a[2][2]<0&&a[1][1]>0&&a[1][2]>0)
    a[2][2]=a[1][1]+a[1][2];
}
void produs()
{
 long x[3][3],i,j;
  
    x[1][1]=a[1][1]*b[1][1]+b[2][1]*a[1][2];
    x[1][2]=a[1][1]*b[1][2]+a[1][2]*b[2][2];
    x[2][1]=a[2][1]*b[1][1]+a[2][2]*b[2][1];
    x[2][2]=b[1][2]*a[2][1]+a[2][2]*b[2][2];
    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    a[i][j]=x[i][j]%nr;
}
void fib(int x)
{
    if(x!=1)
    {
  
  
    fib(x/2);
    if(x%2==0)
         patrat();
    else
    {
        patrat();
        produs();
    }
echilibrare();
    }
}
void initializare()
{
    a[2][1]=1;  b[2][1]=1;
    a[1][1]=0;
    a[1][2]=1;  b[1][2]=1;
    a[2][2]=1;  b[2][2]=1;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
 
  //  for(i=1;i<=n;i++)
    {
        initializare();
    fib(n);
    printf("%lld\n",a[1][2]%nr);
    }
    return 0;
}