#include<fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int k;
long long sol[3][3],m[3][3],a1,a2,b1,b2;
int main ()
{
f>>k;
m[1][2]=m[2][1]=m[2][2]=sol[1][2]=sol[2][2]=sol[2][1]=1;

while(k)
{
if(k%2)
{
a1=sol[1][1];
a2=sol[1][2];
b1=sol[2][1];
b2=sol[2][2];
sol[1][1]=(a1*m[1][1]%mod+a2*m[2][1]%mod)%mod;
sol[1][2]=(a1*m[1][2]%mod+a2*m[2][2]%mod)%mod;
sol[2][1]=(b1*m[1][1]%mod+b2*m[2][1]%mod)%mod;
sol[2][2]=(b1*m[1][2]%mod+b2*m[2][2]%mod)%mod;
}
a1=m[1][1];
a2=m[1][2];
b1=m[2][1];
b2=m[2][2];
m[1][1]=(a1*a1%mod+a2*b1%mod)%mod;
m[1][2]=(a1*a2%mod+a2*b2%mod)%mod;
m[2][1]=(a1*b1%mod+a2*b2%mod)%mod;
m[2][2]=(a2*b1%mod+b2*b2%mod)%mod;
k/=2;
}
g<<sol[1][1];
return 0;
}