#include <iostream>
#include <fstream>

using namespace std;

const int mod=666013;

class Matrice
{
private:
    int a[3][3],n,m;
public:
    Matrice(const int n,const int m,const int val=0)
    {
        this->n=n;
        this->m=m;
        for (int i=1;i<=this->n;i++)
            for (int j=1;j<=this->m;j++)
                this->a[i][j]=val;
    }
    
    void setValue(int i,int j,int val)
    {
        if (i>=1&&i<=this->n&&j>=1&&j<=this->m)
            this->a[i][j]=val;
    }
    
    int getN()
    {
        return this->n;
    }
    
    int getM()
    {
        return this->m;
    }
    
    int getVal(int i,int j)
    {
        return this->a[i][j];
    }
    
    virtual bool samesize(Matrice *m1,Matrice *m2)
    {
        if (m1->n==m2->n&&m1->m==m2->m)
            return true;
        return false;
    }
    
    Matrice& operator=(Matrice *m)
    {
        if (samesize(this, m))
            for (int i=1;i<=this->n;i++)
                for (int j=1;j<=this->m;j++)
                    this->a[i][j]=m->a[i][j];
        return *this;
    }
    
    Matrice& operator*=(Matrice *m)
    {
        if (this->getM()==m->getN())
        {
            Matrice c(this->n,m->m,0);
            for (int i=1; i<=this->n; i++)
                for (int j=1; j<=m->m; j++)
                    for (int k=1; k<=this->m; k++)
                        c.a[i][j]=(c.a[i][j]+1LL*this->a[i][k]*m->a[k][j])%mod;
            *this=c;
        }
        return *this;
    }
    
    Matrice& operator*=(int val)
    {
        for (int i=1;i<=this->n;i++)
            for (int j=1;j<=this->m;j++)
                this->a[i][j]*=val;
        return *this;
    }
    
    Matrice operator*(Matrice &m2)
    {
        Matrice m3=*this;
        m3*=&m2;
        return m3;
    }
    
    Matrice operator*(int val)
    {
        Matrice m3=*this;
        m3*=val;
        return m3;
    }
};

int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    int k;
    Matrice c(2,2),z(2,2,1);
    ///c[2][2]= {1,1,0,0}
    c.setValue(1, 1, 1);
    c.setValue(1, 2, 1);
    ///z[2][2]= {1,1,1,0}
    z.setValue(2, 2, 0);
    
    fin>>k;
    k-=2;
    while(k>1)
        if (k%2==0)
        {
            z*=&z;
            k/=2;
        }
        else
        {
            c*=&z;
            k--;
        }
    c*=&z;
    fout<<c.getVal(1, 1);
    return 0;
}