#include<fstream>
#define MOD 666013
using namespace std;

long long k;
long long a[5];

void citire()
{
 ifstream fin("kfib.in");
 
 fin>>k;
 
 fin.close();
}


void inm(long long x[5], long long y[5])
{ 
 a[1] = ((x[1]*y[1] % MOD) + (x[2]*y[3] % MOD)) % MOD;
 a[2] = ((x[1]*y[2] % MOD) + (x[2]*y[4] % MOD)) % MOD;
 a[3] = ((x[3]*y[1] % MOD) + (x[4]*y[3] % MOD)) % MOD;
 a[4] = ((x[3]*y[2] % MOD) + (x[4]*y[4] % MOD)) % MOD;
}


void copy(long long x[5], long long y[5])
{
 x[1] = y[1]; x[2] = y[2]; x[3] = y[3]; x[4] = y[4];
}


void putere(long long p)
{
 long long b[5],c[5];
 
 if (p != 1)
	 {
	  copy(b,a); copy(c,a);
	  inm(b,c); /*calculez a patrat*/
	  putere(p/2);
	  
	  if (p % 2 == 1) /*daca puterea e impara, mai trebuie inmultit rezultatul inca o data cu a*/
		 {
		  copy(c,a); /*c retine noul a*/
		  inm(b,c); /*inmultesc a-ul curent cu a-ul ridicat la p-1*/
		 }
	 }
}


void solve()
{
 a[1] = 0; a[2] = a[3] = a[4] = 1;
 putere(k-1);
}


void afisare(int nr)
{
 ofstream fout("kfib.out");
 
 fout<<nr<<'\n';
 
 fout.close();
}


int main()
{
	
 citire();
 if (k > 1)
	 {
	  solve();
	  afisare(a[4]);
	 } else
	 afisare(k);
	
 return 0;
}