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