#include <cstdio>
#define infile "kfib.in"
#define outfile "kfib.out"
#define MOD 666013
#define ll long long

ll a,b,c,d,N;

void matrice(ll &a,ll &b,ll &c,ll &d,ll P)
{
      if(P==1)
      {
            a=0; b=c=d=1;
            return;
      }

      matrice(a,b,c,d,P/2);
      if(P%2==0)
      {
            ll a1,b1,c1,d1;
            a1 = ( (a*a) % MOD + (b*c) % MOD ) % MOD; b1 = (b * (a+d) % MOD) % MOD;
            c1 = (c * (a+d) % MOD) % MOD; d1 = ( (d*d) % MOD + (b*c) % MOD ) % MOD;
            a=a1; b=b1; c=c1; d=d1;
            return;
      }

      ll a1,b1,c1,d1;
      a1 = ( (a*a) % MOD + (b*c) % MOD ) % MOD; b1 = (b * (a+d) % MOD) % MOD;
      c1 = (c * (a+d) % MOD) % MOD; d1 = ( (d*d) % MOD + (b*c) % MOD ) % MOD;
      a=b1; b = (a1 + b1) % MOD; c=d1; d = (c1 + d1) % MOD;
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      scanf("%lld",&N);
      matrice(a,b,c,d,N-1);
      printf("%lld\n",d);

      fclose(stdin);
      fclose(stdout);
      return 0;
}