#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long int m[3][3], h[3][3];
void matrice ()
{
    m[1][2]=m[2][1]=m[2][2]=1;
    h[1][2]=h[2][1]=h[2][2]=1;
}
void inm (long long int m[3][3],long long int h[3][3])
{
    int a, b, c, d;
    a=m[1][1]*h[1][1]+m[1][2]*h[2][1];
    b=m[2][1]*h[1][1]+m[2][2]*h[2][1];
    c=m[1][1]*h[1][2] +m[1][2]*h[2][2];
    d=m[2][1]*h[1][2]+m[2][2]*h[2][2];
    m[1][1]=a;
    m[2][1]=b;
    m[1][2]=c;
    m[2][2]=d;
}
void putere (int n)
{   int p=1;
   while (p<n)
     if(p*2<=n)
           inm(m, m),p*=2;
        else
            inm(m,h), p++;
}
void citire ()
{
    int k;
    matrice();
    while(f>>k)
    {
        putere(k);
        g<<m[1][2]%mod<<"\n";
    }
    f.close();
    g.close();
}
int main()
{
    citire();
}