#include <fstream>

using namespace std;
int const mod = 666013;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
class mat{
    public:
    int v [2][2];
    mat (int x){
        v [0][0] = v [1][1] = x;
        v [0][1] = v [1][0] = 0;
    }
    mat (){
        v [0][0] = v [1][0] = v [0][1] = v [1][1] = 0;
    }
    void give (mat X){
        for(int i = 0 ; i < 2 ; ++ i)
            for(int j = 0 ; j < 2 ; ++ j)
                v [i][j] = X.v [i][j];
    }
    mat operator * (mat X) const{
        mat r;
        for(int i = 0 ; i < 2 ; ++ i)
            for(int j = 0 ; j < 2 ; ++ j)
                for(int k = 0 ; k < 2 ; ++ k)
                    r.v [i][j] += (1LL * v [i][k] * X.v [k][j]) % mod;
        return r;
    }
    mat operator ^ (int p){
        mat r (1) , c = (*this);
        for(int i = 0 ; (1 << i) <= p ; ++ i){
            if ((1 << i) & p)
                r = r * c;
            c = c * c;
        }
        return r;
    }
};
int main()
{
    int k;
    f >> k;
    if (k == 0){
        g << 0;
        return 0;
    }
    -- k;
    mat M;
    M.v [0][0] = M.v [0][1] = M.v [1][0] = 1;
    mat r = (M ^ k);
    g << (1LL * r.v [1][0] + r.v [1][1]) % mod;
    return 0;
}