#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("kfib.in");
ofstream out("kfib.out");
 
typedef long long ll;
const ll MOD = 666013;
 
class matrix {
public:
    vector< vector< ll > > m_data;
 
    matrix() {
        m_data.resize(2, vector< ll > (2));
 
        m_data[0][0] = 1; m_data[0][1] = 0;
        m_data[1][0] = 0; m_data[1][1] = 1;
    }
 
    matrix(ll a) {
        m_data.resize(2, vector< ll >(2));
 
        m_data[0][0] = 0; m_data[0][1] = 1;
        m_data[1][0] = a; m_data[1][1] = a;
    }
 
    matrix(const matrix &other) {
        this->m_data.resize(2, vector< ll >(2));
 
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                this->m_data[i][j] = other.m_data[i][j];
            }
        }
    }
 
    matrix& operator=(const matrix &other) {
        if(this == &other) {
            return *this;
        }
 
        this->m_data.resize(2, vector< ll >(2));
 
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                this->m_data[i][j] = other.m_data[i][j];
            }
        }
 
        return *this;
    }
 
    matrix operator*(const matrix &other) const {
        matrix result;
 
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                ll newElement = 0;
                for(int k = 0; k < 2; ++k) {
                    newElement += (this->m_data[i][k] * other.m_data[k][j]);
                }
 
                result.m_data[i][j] = newElement;
            }
        }
 
        return result;
    }
 
    ~matrix() {
        for(int i = 0; i < 2; ++i) {
            m_data[i].clear();
        }
        m_data.clear();
    }
};
 
matrix modulo(const matrix &other) {
    matrix result = other;
 
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            result.m_data[i][j] %= MOD;
        }
    }
 
    return result;
}
 
matrix lgput(matrix n, ll p) {
    if(p == 0) {
        matrix identicalMatrix;
        return identicalMatrix;
    }
    if(p == 1) {
        return n;
    }
 
    if(p % 2 == 0) {
        return modulo(lgput(modulo(n * n), p / 2));
    } else {
        return modulo(n * lgput(modulo(n * n), p / 2));
    }
}
 
int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int n; in >> n;

    matrix m = matrix(1);
    matrix result = lgput(m, n - 1);

    out << result.m_data[1][1] << "\n";
 
    in.close(); out.close();
 
    return 0;
}