#define md 666013
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

 
void matricein(long a[2][2],long b[2][2])
{int i,j,k;
long c[2][2]={{0,0},{0,0}};

for(i=0;i<2;i++)
  for(j=0;j<2;j++)
    for(k=0;k<2;k++)
      c[i][j]=c[i][j]+((a[i][k]*b[k][j])%md)%md;

for(i=0;i<2;i++)
      for(j=0;j<2;j++)
         a[i][j]=c[i][j];                  
}

void power(long x[2][2],long n)
{ 
long rez[2][2]={{1,0},{0,1}};

while (n)
	{
	if (n & 1)
		{
		matricein(rez,x);//rez =rez*x;
		n--;
		}
		matricein(x,x);//x =x*x;
		n >>=1 ;
	}
	
int i,j;
for(i=0;i<2;i++)
      for(j=0;j<2;j++)
         x[i][j]=rez[i][j];   
}

int main()
{long n,b[2][2]={{0,1},{1,1}};
f>>n;
power(b,n-2);
g<<b[1][1]; 
return 0;     
}