#include <fstream>
#include <cstring>
using namespace std;
static const int LIM=3,MOD=666013;
typedef long long ll;
int main()
{
    fstream f("kfib.in",fstream::in),g("kfib.out",fstream::out);
    int nr,a[LIM][LIM]= {},b[LIM][LIM]= {},c[LIM][LIM]= {},i,j,k;
    f>>nr;
    f.close();
    a[1][1]=a[2][1]=a[1][2]=b[1][1]=b[2][2]=1;
    while(nr)
    {
        if(nr%2)
        {
            memset(c,0,sizeof(c));
            for(i=1; i<=2; ++i)
            {
                for(j=1; j<=2; ++j)
                {
                    for(k=1; k<=2; ++k) c[i][j]=(c[i][j]+(ll)a[i][k]*b[k][j])%MOD;
                }
            }
            memcpy(b,c,sizeof (c));
        }
        memset(c,0,sizeof (c));
        for(i=1; i<=2; ++i)
        {
            for(j=1; j<=2; ++j)
            {
                for(k=1; k<=2; ++k) c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%MOD;
            }
        }
        memcpy(a,c,sizeof (c));
        nr/=2;
    }
    g<<b[2][1]<<"\n";
    g.close();
    return 0;
}