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

ifstream f("kfib.in");
ofstream g("kfib.out");

struct Matrice{
    int a[3][3];

    Matrice(){
        a[0][0] = 0;
        a[0][1] = a[1][0] = a[1][1]  = 1;
    }

    void zeroz(){
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
    }
    void identity(){
        a[0][0] = a[1][1] = 1;
        a[0][1] = a[1][0] = 0;
    }
    Matrice &operator*(const Matrice &a){
        Matrice rez;
        rez.zeroz();
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                for(int k=0; k<2; k++)
                    rez.a[i][j] += ((1LL*(this->a[i][k]) * (this->a[k][j]))%MOD);
        return rez;
    }


    Matrice& operator=(const Matrice &b){
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
                this->a[i][j] = b.a[i][j];
        return *this;
    }


};

Matrice inmult(Matrice a, Matrice b){
    Matrice rez;
    rez.zeroz();
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                rez.a[i][j] += ((1LL*(a.a[i][k]) * (b.a[k][j]))%MOD);
    return rez;
}

Matrice ridicare_putere(Matrice a, int p){
    Matrice rez;
    rez.identity();
    while(p!=0)
    {
        if(p%2 ==1)
        {
            p--;
            rez=inmult(rez, a);
        }
        p/=2;
        a=inmult(a, a);
    }
    return rez;
}


int main()
{
    int n;
    f>>n;
    Matrice a = Matrice();
    Matrice rez = ridicare_putere(a, n-1);

    g<<(rez.a[1][1]%MOD);
    return 0;
}