#include <fstream>
const int MOD=666013;
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

struct matrice
{
    long long x1,x2,y1,y2;
}A;

void inmultire(matrice &c,matrice b)
{
    matrice a=c;
    c.x1=(a.x1*b.x1%MOD+a.x2*b.y1%MOD)%MOD;
    c.x2=(a.x1*b.x2%MOD+a.x2*b.y2%MOD)%MOD;
    c.y1=(a.y1*b.x1%MOD+a.y2*b.y1%MOD)%MOD;
    c.y2=(a.y1*b.x2%MOD+a.y2*b.y2%MOD)%MOD;
}

 int logexp(int p)
{
    matrice val={1,0,0,1},B={1,1,1,0};
    while(p>0)
    {
        if(p%2!=0)
            inmultire(val,B);
        inmultire(B,B);
        p/=2;
    }
    return val.x1;
}

int main()
{
    int n;
    f>>n;
    A={1,1,1,0};
    g<<logexp(n-1);
    return 0;
}