#include <iostream>
#include <cstdio>
#define mod 666013

using namespace std;

class matrice
{
private:
    int n, a[5][5];
public:
    matrice()
    {
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
                a[i][j]=0;
        n=0;
    }
    matrice(int nn, int x)
    {
        n=nn;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                a[i][j]=x;
    }
    matrice(int nn)
    {
        n=nn;
        a[0][0]=0;
        a[0][1]=1;
        a[1][0]=1;
        a[1][1]=1;
    }
    int* operator[](const int i)
    {
        return this->a[i];
    }
    void setElem(int i, int j, int x)
    {
        a[i][j]=x;
    }
    int getElem(int i, int j)
    {
        return a[i][j];
    }
    void setN(int x)
    {
        n=x;
    }
    int getN()
    {
        return n;
    }
    matrice &operator =(const matrice &b)
    {
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                this->a[i][j]=b.a[i][j];
        return *this;
    }
    matrice operator +(const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                c[i][j]=this->a[i][j]+b.a[i][j];
        c.n=nn;
        return c;
    }
    matrice operator -(const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                c[i][j]=this->a[i][j]-b.a[i][j];
        c.n=nn;
        return c;
    }
    matrice operator * (const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                for(int k=0;k<nn;k++)
                    c[i][j]=((1LL*c[i][j])%mod+1LL*(1LL*(1LL*this->a[i][k]%mod)*(1LL*b.a[k][j]%mod)%mod))%mod;
        c.n=nn;
        return c;
    }
    void putere(int p, matrice &c, const matrice b)
    {
        if(p==1)
            return;
        if(p%2==0)
        {
            (*this).putere(p/2, c, b);
            c=c*c;
            *this=c;
//            cout<<p<<"\n";
//            c.afisare();
        }
        else
        {
            (*this).putere(p-1, c, b);
            c=c*b;
            *this=c;
//            cout<<p<<"\n";
//            c.afisare();
        }
    }
    void afisare()
    {
        int nn=this->n;
        for(int i=0;i<nn;i++)
        {
            for(int j=0;j<nn;j++)
                cout<<this->a[i][j]<<" ";
            cout<<"\n";
        }
    }
};

matrice a=matrice(2);
int k;

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%d", &k);
    a.putere(k-1, a, a);
    printf("%d", a.getElem(1, 1));
}