#include <iostream>
#include <fstream>
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()
{
    ull k,f1=0,f2=1;
    base.a=0;base.b=1;base.c=1;base.d=1;
    res.a=1;
    res.b=0;
    res.c=0;
    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);

}