#include <iostream>
#include <fstream>
//http://www.infoarena.ro/problema/kfib
using namespace std;
#define ull unsigned long long int
#define m 666013
ifstream in("kfib.in");
ofstream out("kfib.out");
struct matrice{
ull a,b,c,d;} base,res;
int main()               //Idea de rezolvare e simpla, definim al k termen fibonacci printr-o recurenta (fn-2 fn-1)(0 1)=(fn-1 fn)
{//                                                                                                       ||      (1 1)
    ull k,f1=0,f2=1;//                                                                                    Mi       |||
    base.a=0;base.b=1;base.c=1;base.d=1;//                                                                         Z  => Mi=Z*Mi-1=Z^(i-1)*M1 si deci
    res.a=1;//                                                                                                      calculam Z^(i-1) in timp logaritmic
    res.b=0;//
    res.c=0;// in res vom tine matricea Z^(i-1) si la final afisam res.d deoarece f0=0 si f1=1 deci f0*res.b+f1*res.d=res.d
    res.d=1;//
    in>>k;
    k--;
    struct matrice s;
    while(k)
    {
        if(k&1)
          {
              s.a = ( ((res.a%m)*(base.a%m))%m+((res.b%m)*(base.c%m))%m )%m;
              s.b = ( ((res.a%m)*(base.b%m))%m+((res.b%m)*(base.d%m))%m )%m;
              s.c = ( ((res.c%m)*(base.a%m))%m+((res.d%m)*(base.c%m))%m )%m;
              s.d = ( ((res.c%m)*(base.b%m))%m+((res.d%m)*(base.d%m))%m )%m;
              res = s;
          }

        s.a = ( ((base.a%m)*(base.a%m))%m+((base.b%m)*(base.c%m))%m )%m;
        s.b = ( ((base.a%m)*(base.b%m))%m+((base.b%m)*(base.d%m))%m )%m;
        s.c = ( ((base.c%m)*(base.a%m))%m+((base.d%m)*(base.c%m))%m )%m;
        s.d = ( ((base.c%m)*(base.b%m))%m+((base.d%m)*(base.d%m))%m )%m;
        base = s;
        k=k>>1;
     }
      out<<(res.d);
}