#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout("kfib.out");

#define ll long long
class Matrix
{
private:
    int N, M;
    ll **matrix;
public:
    Matrix(int n = 0, int m = 0)
    {
        N = n;
        M = ( n > m )? n : m;
        matrix = new ll*[N];
        for(int i = 0 ; i < N ; ++i)
            matrix[i] = new ll[M];
    }

    int rows()
    {
        return N;
    }
    int cols()
    {
        return M;
    }
    ll a(int i, int j)
    {
        return matrix[i][j];
    }

    void ch_a(int i, int j, ll val)
    {
        matrix[i][j] = val;
    }

    Matrix operator *(Matrix mat)
    {
        Matrix m( this->rows() , mat.cols() );

        for(int i = 0 ; i < m.rows() ; ++i)
            for(int j = 0 ; j < m.cols() ; ++j)
            {
                int val = 0;
                for(int k = 0 ; k < this->cols() ; ++k)
                    val += ( this->a(i,k)*mat.a(k,j) )%666013;
                m.ch_a(i,j,val);
            }

        return m;
    }
};

Matrix expo(Matrix a, long long b)
{
    Matrix aux(2);

    aux.ch_a(0,0,1);
    aux.ch_a(0,1,0);
    aux.ch_a(1,0,0);
    aux.ch_a(1,1,1);

    while( b != 1 )
    {
        if( b % 2 == 1 )
           aux = aux * a;
        a = a*a;
        b /= 2;
    }
    return aux*a;
}

int main()
{
    ll K, Fk;

    Matrix a(2);
    a.ch_a(0,0,0);
    a.ch_a(0,1,1);
    a.ch_a(1,0,1);
    a.ch_a(1,1,1);

    Matrix f(1,2);
    f.ch_a(0,0,0);
    f.ch_a(0,1,1);

    fin >> K;
    if( K == 0 )
        Fk = 0;
    else
    {
        a = expo(a, K-1);
        f = f*a;
        Fk = f.a(0,1)%666013;
    }
    fout << Fk;
    return 0;
}