#include <utility>
#include <iostream>
#undef minor

template<class T, T mod>
class Modular {
    public:
        Modular() : value() {}
        Modular(const Modular &x) : value(x.value) {}
        Modular(T x) {
            while (x < 0) {
                x += mod;
            }
            value = x % mod;
        }
        // use the default operator=
        Modular &operator+=(const Modular &x) {
            value += x.value;
            value %= mod;
            return *this;
        }
        Modular &operator-=(const Modular &x) {
            value += mod;
            value -= x.value;
            value %= mod;
            return *this;
        }
        Modular &operator*=(const Modular &x) {
            value *= x.value;
            value %= mod;
            return *this;
        }
        Modular &operator/=(const Modular &x) {
            return *this *= ~x;
        }
        Modular operator+() const {
            return *this;
        }
        Modular operator-() const {
            return 0 - *this;
        }
        Modular operator~() const {

        }
        Modular &operator++() {
            ++value;
            value %= mod;
            return *this;
        }
        Modular &operator--() {
            value += mod;
            --value;
            value %= mod;
            return *this;
        }
        Modular operator++(int) {
            Modular c = *this;
            ++*this;
            return c;
        }
        Modular operator--(int) {
            Modular c = *this;
            --*this;
            return c;
        }
        operator T() const {
            return value;
        }
        operator bool() const {
            return value;
        }
    private:
        T value;
        static std::pair<T, T> egcd(const T &a, const T &b) {
            if (!b) return std::pair<T, T>(1, 0);
            T q, r;
            std::pair<T, T> res;
            q = a / b;
            r = a % b;
            res = egcd(b, r);
            return std::pair<T, T>(res.second, res.first - q * res.second);
        }
};

template<class T, T mod>
Modular<T, mod> operator+(const Modular<T, mod> &a, const Modular<T, mod> &b) {
    Modular<T, mod> c = a;
    return c += b;
}

template<class T, T mod>
Modular<T, mod> operator-(const Modular<T, mod> &a, const Modular<T, mod> &b) {
    Modular<T, mod> c = a;
    return c -= b;
}

template<class T, T mod>
Modular<T, mod> operator*(const Modular<T, mod> &a, const Modular<T, mod> &b) {
    Modular<T, mod> c = a;
    return c *= b;
}

template<class T, T mod>
Modular<T, mod> operator/(const Modular<T, mod> &a, const Modular<T, mod> &b) {
    Modular<T, mod> c = a;
    return c /= b;
}

template<class T, unsigned n, unsigned m>
struct Matrix {
    public:
        Matrix() : data() {
        }
        Matrix(const Matrix<T, n, m> &x) {
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < m; ++j) {
                    data[i][j] = x[i][j];
                }
            }
        }
        // use the default operator=
        Matrix<T, n, m> &operator+=(const Matrix<T, n, m> &x) {
            for (unsigned i=0; i<n; ++i) {
                for (unsigned j=0; j<n; ++j) {
                    data[i][j] += x[i][j];
                }
            }
            return *this;
        }
        Matrix<T, n, m> &operator-=(const Matrix<T, n, m> &x) {
            for (unsigned i=0; i<n; ++i) {
                for (unsigned j=0; j<n; ++j) {
                    data[i][j] -= x[i][j];
                }
            }
            return *this;
        }
        Matrix<T, n, m> &operator*=(const T &x) {
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < m; ++j) {
                    data[i][j] *= x;
                }
            }
            return *this;
        }
        Matrix<T, n, m> &operator/=(const T &x) {
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < m; ++j) {
                    data[i][j] /= x;
                }
            }
            return *this;
        }
        template<unsigned p>
            Matrix<T, n, p> operator*(const Matrix<T, m, p> &x) const {
                Matrix<T, n, p> ans;
                for(unsigned i=0; i<n; ++i) {
                    for (unsigned j=0; j<p; ++j) {
                        ans[i][j] = 0;
                        for (unsigned k=0; k<m; ++k) {
                            ans[i][j] += data[i][k] * x[k][j];
                        }
                    }
                }
                return ans;
            }
        T (&operator[](unsigned index))[m] {
            return data[index];
        }
        const T (&operator[](unsigned index) const)[m] {
            return data[index];
        }
        Matrix<T, m, n> transpose() const {
            Matrix<T, m, n> ans;
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < m; ++j) {
                    ans[j][i] = data[i][j];
                }
            }
            return ans;
        }
    private:
        T data[n][m];
};

template<class T, unsigned n, unsigned m>
Matrix<T, n, m> operator+(const Matrix<T, n, m> &x, const Matrix<T, n, m> &y) {
    Matrix<T, n, m> t = x;
    t+=y;
    return t;
}
template<class T, unsigned n, unsigned m>
Matrix<T, n, m> operator-(const Matrix<T, n, m> &x, const Matrix<T, n, m> &y) {
    Matrix<T, n, m> t = x;
    t-=y;
    return t;
}
template<class T, unsigned n, unsigned m>
Matrix<T, n, m> operator*(const Matrix<T, n, m> &x, const T &y) {
    Matrix<T, n, m> t = x;
    t*=y;
    return t;
}
template<class T, unsigned n, unsigned m>
Matrix<T, n, m> operator*(const T &y, const Matrix<T, n, m> &x) {
    return x * y;
}
template<class T, unsigned n, unsigned m>
Matrix<T, n, m> operator/(const Matrix<T, n, m> &x, const T &y) {
    Matrix<T, n, m> t = x;
    t/=y;
    return t;
}

template<class T, unsigned n>
struct Square_matrix : public Matrix<T, n, n> {
    public:
        Square_matrix() {
        }
        Square_matrix(const Matrix<T, n, n> &x) : Matrix<T, n, n>(x) {
        }
        Square_matrix(const T &x) {
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < n; ++j) {
                    (*this)[i][j] = (i == j ? x : T(0));
                }
            }
        }
        Square_matrix<T, n-1> minor(unsigned x, unsigned y) const {
            Square_matrix<T, n-1> ans;
            for (unsigned i = 0; i < n-1; ++i) {
                for (unsigned j = 0; j < n-1; ++j) {
                    ans[i][j] = (*this)[i<x ? i : i+1][j<y ? j : j+1];
                }
            }
            return ans;
        }
        Square_matrix operator*=(const Square_matrix &x) {
            return *this = *this * x;
        }
        T cofactor(unsigned x, unsigned y) const {
            return (((x+y)%2)?-1:1) * minor(x, y).determinant();
        }
        T determinant() const {
            T ans=0;
            for (unsigned i = 0; i < n; ++i) {
                ans += (*this)[0][i] * cofactor(0, i);
            }
            return ans;
        }
        Square_matrix<T, n> adjoint() const {
            Square_matrix ans;
            for (unsigned i = 0; i < n; ++i) {
                for (unsigned j = 0; j < n; ++j) {
                    ans[j][i] = cofactor(i, j);
                }
            }
            return ans;
        }
        Square_matrix<T, n> inverse() const {
            return adjoint() / determinant();
        }
};

template<class T>
struct Square_matrix<T, 0> : public Matrix<T, 0, 0> {
    public:
        Square_matrix() {
        }
        Square_matrix(const Matrix<T, 0, 0> &x) : Matrix<T, 0, 0>(x) {
        }
        T determinant() const {
            return 1;
        }
        Square_matrix<T, 0> adjoint() const {
            return Square_matrix<T, 0>();
        }
        Square_matrix<T, 0>inverse() const {
            return Square_matrix<T, 0>();
        }
};

template<class T> T pow(T a, unsigned b) {
    T ans(1);
    while (b) {
        if (b % 2) {
            ans *= a;
            --b;
        }
        a *= a;
        b /= 2;
    }
    return ans;
}

int main() {
    int n;
    std::cin >> n;
    while (n != -1) {
        Square_matrix<Modular<unsigned, 10000>, 2> a;
        a[0][0] = 1;
        a[0][1] = 1;
        a[1][0] = 1;
        a[1][1] = 0;
        Square_matrix<Modular<unsigned, 10000>, 2> ans = pow(a, n);
        std::cout << unsigned(ans[0][1]) << '\n';
        std::cin >> n;
    }
}