#include<cstdio>
#define mod 666013
using namespace std;
long long a[5][5],p[5][5];
long long x,y,z,w,x1,y1,z1,w1;
int n,k,b[100000],i;
void transf(int r)
{
    while(r>0)
    {
        b[++k]=r%2;
        r=r/2;
    }
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    --n;
    transf(n);
    p[1][1]=1;p[2][2]=1;
    a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
    for (i=k;i>=1;--i)
    {
        x=((p[1][1]*p[1][1])%mod+(p[1][2]*p[2][1])%mod)%mod;
        y=((p[1][1]*p[1][2])%mod+(p[1][2]*p[2][2])%mod)%mod;
        z=((p[2][1]*p[1][1])%mod+(p[2][2]*p[2][1])%mod)%mod;
        w=((p[2][1]*p[1][2])%mod+(p[2][2]*p[2][2])%mod)%mod;
        if (b[i]==1)
        {
            x1=((a[1][1]*x)%mod+(a[2][1]*y)%mod)%mod;
            y1=((a[1][2]*x)%mod+(a[2][2]*y)%mod)%mod;
            z1=((a[1][1]*z)%mod+(a[2][1]*w)%mod)%mod;
            w1=((a[1][2]*z)%mod+(a[2][2]*w)%mod)%mod;
            p[1][1]=x1;p[1][2]=y1;p[2][1]=z1;p[2][2]=w1;
        }
        else
        {
         p[1][1]=x;p[1][2]=y;p[2][1]=z;p[2][2]=w;
        }
    }
    printf("%d\n",p[2][2]);
    return 0;
}