#include<fstream>
using namespace std;
long long k,a,b,c,d;
const int m=666013;
ifstream f("kfib.in");
ofstream g("kfib.out");
void fct(long long k)
{if(k==1)
{b++;
c++;
d++;
}
else
{fct(k/2);
long long ap=(a*a+b*c)%m;
long long bp=(b*(a+d))%m;
long long cp=(c*(a+d))%m;
long long dp=(d*d+b*c)%m;
a=ap;
b=bp;
c=cp;
d=dp;
if(k%2)
{ap=b;
bp=(a+b)%m;
cp=d;
dp=(c+d)%m;
a=ap;
b=bp;
c=cp;
d=dp;
}
}
}
int main()
{f>>k;
if(!k)
g<<0;
else
{fct(k);
g<<c;
}
return 0;
}