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