#include<fstream>
#define tip long long
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const tip MOD=666013;
struct tri
{
    tip a1,a2,a3;
};
tri a,r,produs(tri,tri);
int n;
int main()
{
    f>>n;
    a.a1=a.a2=1;a.a3=0;
    r.a1=r.a3=1;r.a2=0;
    while(n)
    {
        if(n%2)
            r=produs(r,a);
        a=produs(a,a);
        n=n/2;
    }
    g<<r.a2;
    return 0;
}
tri produs(tri A,tri B)
{
    tri R;
    R.a1=(A.a1*B.a1+A.a2*B.a2)%MOD;
    R.a2=(A.a1*B.a2+A.a2*B.a3)%MOD;
    R.a3=(A.a2*B.a2+A.a3*B.a3)%MOD;
    return R;

}