#include<fstream>
using namespace std;
ifstream F("kfib.in");
ofstream G("kfib.out");
long long n,m=666013,a,b,c,d,e,f,g,h,i,j,k;
int main()
{
    for(F>>n,--n,e=h=b=c=d=1;n;n>>=1,i=(a*a+b*c)%m,j=(a*b+b*d)%m,k=(c*a+d*c)%m,d=(c*b+d*d)%m,a=i,b=j,c=k)
        if(n&1)
            i=(e*a+f*c)%m,j=(e*b+f*d)%m,k=(g*a+h*c)%m,h=(g*b+h*d)%m,e=i,f=j,g=k;
    return G<<h,0;
}