#include <iostream>
#include <fstream>
#include <cstring>

#define MOD 666013

using namespace std;

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

class matrix{
private:
    static const int DIM=2;
public:
    int v[DIM][DIM];
    matrix (){
        memset(v,0,sizeof(v));
    };
    void unit(){
        for (int i=0;i<DIM;++i)
            v[i][i]=1;
    }
    matrix operator *(matrix a){
        matrix aux;
        for (int i=0;i<DIM;++i)
            for (int j=0;j<DIM;++j)
                for (int k=0;k<DIM;++k)
                aux.v[i][j]=(aux.v[i][j]+1LL*v[i][k]*a.v[k][j])%MOD;
        return aux;
    }
};

matrix lgput(matrix base,int exponent){
    matrix return_val;
    return_val.unit();
    for (;exponent;exponent>>=1){
        if (exponent&1)
            return_val=return_val*base;
        base=base*base;
    }
    return return_val;
}

int main()
{
    int n;
    matrix b;
    b.v[0][1]=b.v[1][0]=b.v[1][1]=1;
    f>>n;
    b=lgput(b,n);
    t<<b.v[1][0];
    return 0;
}