#include <iostream>
#include <fstream>

using namespace std;

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

const int M = 666013;

class mat2{
public:
    long long a, b, c, d;
    mat2(long long a1, long long a2, long long a3, long long a4){
        a = a1; b = a2; c = a3; d = a4;
    }
    mat2 operator+(const mat2& B){
        mat2 A(0, 0, 0, 0);
        A.a = this -> a + B.a;
        A.b = this -> b + B.b;
        A.c = this -> c + B.c;
        A.d = this -> d + B.d;
        return A;
    }
    void operator+=(const mat2& B){
        (*this) = (*this) + B;
    }
    mat2 operator-(const mat2& B){
        mat2 A(0, 0, 0, 0);
        A.a = this -> a - B.a;
        A.b = this -> b - B.b;
        A.c = this -> c - B.c;
        A.d = this -> d - B.d;
        return A;
    }
    void operator-=(const mat2& B){
        (*this) = (*this) - B;
    }
    mat2 operator-(){
        mat2 O2(0, 0, 0, 0);
        return O2 - *this;
    }
    mat2 operator*(const mat2& B){
        mat2 A(0, 0, 0, 0);
        A.a = ((this -> a) * B.a + (this -> b) * B.c) % M;
        A.b = ((this -> a) * B.b + (this -> b) * B.d) % M;
        A.c = ((this -> c) * B.a + (this -> d) * B.c) % M;
        A.d = ((this -> c) * B.b + (this -> d) * B.d) % M;
        return A;
    }
    void operator*=(const mat2& B){
        (*this) = (*this) * B;
    }
    mat2 operator*(const int& x){
        mat2 A(0, 0, 0, 0);
        A.a = (this -> a) * x;
        A.b = (this -> b) * x;
        A.c = (this -> c) * x;
        A.d = (this -> d) * x;
        return A;
    }
    void operator*=(const int& x){
        (*this) = (*this) * x;
    }
    bool operator==(const mat2& B){
        return (this -> a == B.a) && (this -> b == B.b) && (this -> c == B.c) && (this -> d == B.d);
    }
    bool operator!=(const mat2& B){
        return !((*this) == B);
    }
    int tr(){
        return a + d;
    }
    int det(){
        return a*d - b*c;
    }
    ///fA - polinomul caracteristic matricei A
    int f(int x){
        mat2 I2(1, 0, 0, 1);
        return (I2 * x - *this).det();
        ///return x * x - tr() * x + det();
    }
    mat2 f(mat2 X){
        mat2 I2(1, 0, 0, 1);
        return I2 * (X - *this).det();
        ///return X * X - X * tr() + I2 * det();
    }

    void print(){
        cout << a << " " << b << '\n' << c << " " << d << '\n';
    }
private:

};

mat2 I2(1, 0, 0, 1), O2(0, 0, 0, 0);

mat2 operator*(int x, mat2 A){
    A *= x;
    return A;
}

mat2 pow(mat2 A, int x){
    mat2 P = I2;
    if(x == 0){
        return I2;
    }
    while(x){
        if(x & 1){
            P *= A;
        }
        x = x >> 1;
        A *= A;
    }
    return P;
}

int main()
{
    int n;
    mat2 A(1, 1, 1, 0);
    in >> n;
    out << pow(A, n).c;
    return 0;
}