#include <fstream>
using namespace std;

const long long C = 666013;

void Inmulteste(long long A1,long long A2,long long A3,long long A4,
                long long B1,long long B2,long long B3,long long B4,
                long long &C1,long long &C2,long long &C3,long long &C4)
{
 C1 = (A1*B1 + A2*B3) % C;
 C2 = (A1*B2 + A2*B4) % C;
 C3 = (A3*B1 + A4*B3) % C;
 C4 = (A3*B2 + A4*B4) % C;
}

int main(void)
{
 fstream fin("kfib.in",ios::in);
 fstream fout("kfib.out",ios::out);
 long long N,M1,M2,M3,M4,TM1,TM2,TM3,TM4;
 fin >> N;
 TM1 = M1 = 0;
 TM2 = M2 = 1;
 TM3 = M3 = 1;
 TM4 = M4 = 1;
 while (N > 0)
  {
   if (N & 1)
     {
      Inmulteste(M1,M2,M3,M4,TM1,TM2,TM3,TM4,M1,M2,M3,M4);
     }
   Inmulteste(TM1,TM2,TM3,TM4,TM1,TM2,TM3,TM4,TM1,TM2,TM3,TM4);
   N = N >> 1;
  }
 fout << M1;
 fin.close();
 fout.close();
 return 0;
}