#include <fstream>
#define p 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void putere(int &a,int &b, int &c, int &d, int n)
{  int a1=a,b1=b,c1=c,d1=d;
   int a2,b2,c2,d2;
   if(n>1)
     if(n%2==1) {putere(a,b,c,d,n-1);
                 a2=a;b2=b;c2=c;d2=d;
                 a=(1LL*a1*a2%p+1LL*b1*c2%p)%p;
                 b=(1LL*a1*b2%p+1LL*b1*d2%p)%p;
                 c=(1LL*a2*c1%p+1LL*d1*c2%p)%p;
                 d=(1LL*c1*b2%p+1LL*d1*d2%p)%p;
                 }
      else { a=(1LL*a1*a1%p+1LL*b1*c1%p)%p;
             b=(1LL*a1*b1%p+1LL*b1*d1%p)%p;
             c=(1LL*a1*c1%p+1LL*d1*c1%p)%p;
             d=(1LL*c1*b1%p+1LL*d1*d1%p)%p;
             putere(a,b,c,d,n/2);
           }
}

int main()
{
    int k,a,b,c,d;
    fin>>k;
    //for(k=1;k<=10;k++)
    { a=0; b=c=d=1;
      putere(a,b,c,d,k);
      fout<<(b)%p<<" ";
    }
    return 0;
}