#include <iostream>
#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
 int k,fib[5][5],m[5][5],m2[5][5];

 void Mult(int a[][5],int b[][5])
 { int i,j,t,l1=a[0][0],c1=a[0][1],l2=b[0][0],c2=b[0][1],res[5][5];

     for(i=1;i<=l1;i++)
      for(j=1;j<=c2;j++)
      { res[i][j]=0;
         for(t=1;t<=c1;t++)
          res[i][j]+=1LL*(a[i][t]%mod)*(b[t][j]%mod)%mod;

        res[i][j]%=mod;
      }

    for(i=1;i<=l1;i++)
     for(j=1;j<=c2;j++)
      a[i][j]=res[i][j];
 }

 void Solve()
 { int i;
   for(i=0;i<=31;i++)
   { if (k&(1LL<<i)) Mult(m,m2);
     Mult(m2,m2);
   }
 }

int main()
{
    f>>k;
   if (k<=1) {g<<k<<"\n"; return 0;}
   fib[0][0]=1; fib[0][1]=2;

   fib[1][1]=0; fib[1][2]=1;
   m[0][0]=m2[0][0]=2; m[0][1]=m2[0][1]=2;
   m[1][1]=1; m[2][2]=1;
   m2[1][1]=0; m2[1][2]=1; m2[2][1]=1; m2[2][2]=1;

    k--;
     Solve();

    Mult(fib,m);

     g<<fib[1][2]<<"\n";

    return 0;
}