#include <bits/stdc++.h>
using namespace std;
struct MATRIX
{
    int v[3][3];
};
const int mod=666013;
MATRIX produs(MATRIX a,MATRIX b)
{
    MATRIX c;
    int i,j;
    c.v[1][1]=c.v[1][2]=c.v[2][1]=c.v[2][2]=0;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
        for(int p=1;p<=2;p++)
            c.v[i][j]=(c.v[i][j]+(1LL*a.v[i][p]*b.v[p][j]))%mod;
        return c;
}
MATRIX rid_put(MATRIX a,int put)
{
    MATRIX rez,l;
    int i,j;
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            l.v[i][j]=a.v[i][j];
    rez.v[1][1]=1;
    rez.v[2][2]=1;
    rez.v[1][2]=0;
    rez.v[2][1]=0;
    while(put)
    {
        if(put&1)rez=produs(rez,l);
        l=produs(l,l);
        put=put>>1;
    }
    return rez;
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    MATRIX a;
    int n;
    scanf("%d",&n);
    a.v[1][1]=0;
    a.v[1][2]=1;
    a.v[2][1]=1;
    a.v[2][2]=1;
    a=rid_put(a,n);
    cout<<a.v[2][1];
    return 0;
}