#include <fstream>
#include <tuple>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef long long Int;
const Int M=666013;
typedef tuple<Int,Int,Int> ob;
ob operator * (ob X,ob Y)
{
    Int a,b,c,x,y,z;
    tie(a,b,c)=X;
    tie(x,y,z)=Y;
    return ob((a*x+b*y)%M,(a*y+b*z)%M,(b*y+c*z)%M);
}
ob Pow(int e)
{
    if(e==0) return ob(1,0,1);
    ob s=Pow(e/2);
//    s=s*s;
//    if(e%2)
//        s=s*ob(1,1,0);
    return e%2?s*s*ob(1,1,0):s*s;
}
int main()
{
    int k;
    fin>>k;
    fout<<get<1>(Pow(k));
    return 0;

}