#include <bits/stdc++.h>
using namespace std;

namespace MMNMM {
    template<class UnsignedInteger = unsigned long, UnsignedInteger Mod = 1000000007>
    class modint {
        static_assert(Mod & 1, "mod mast be odd");

        using value_type = UnsignedInteger;
        using const_value = const value_type;
        using reference_type = value_type &;
        using const_reference = const_value &;

        static constexpr size_t bit_length = 32;
        static_assert(Mod < static_cast<UnsignedInteger>(1) << bit_length - 2, "mod is too big");
        static constexpr value_type mask = ~(~static_cast<UnsignedInteger>(0) << bit_length);

        static constexpr value_type f(value_type n) {
            value_type ret = 1;
            for (auto _ = 0; _ < 5; ++_)ret = ret * (2 - ret * n);
            return -ret & mask;
        }

        static constexpr const_value minv{f(Mod)};
        static constexpr const_value r2{-Mod % Mod};
        static constexpr const_value r{(static_cast<UnsignedInteger>(1) << bit_length) % Mod};

        static constexpr value_type reduce(const_value v) {
            return (v + Mod * ((v * minv) & mask)) >> bit_length;
        }

        value_type val;
        static constexpr value_type upperbound = 2 * Mod;

    public:

        static constexpr value_type e() {
            return 1;
        }

        static constexpr value_type z() {
            return 0;
        }

        static constexpr value_type get_minv() noexcept { return minv; }

        static constexpr value_type get_r2() noexcept { return r2; }

        static constexpr value_type get_mod() noexcept { return Mod; }

        constexpr value_type get_value() const noexcept { return val == Mod ? 0 : reduce(val); }

        constexpr value_type get_raw() const noexcept { return val; }

        constexpr modint() : val(0) {}

        template<class T>
        constexpr modint(const T &_v = 0) : val(reduce(_v * r2)) {}

        template<class UnsignedInteger2, UnsignedInteger2 Mod2>
        constexpr modint(const modint<UnsignedInteger2, Mod2> &_v) : val(reduce(_v.get_value() * r2)) {}

        template<class UnsignedInteger2>
        constexpr modint(const modint<UnsignedInteger2, Mod> &_v) : val(_v.get_raw()) {}

        constexpr modint(const modint &_v) = default;

        constexpr modint operator++(int) noexcept {
            auto t = *this;
            val += r;
            val -= (val >= upperbound) * upperbound;
            return t;
        }

        constexpr modint operator--(int) noexcept {
            auto t = *this;
            val += (val < r) * upperbound;
            val -= r;
            return t;
        }

        constexpr modint &operator++() noexcept {
            val += r;
            val -= (val >= upperbound) * upperbound;
            return *this;
        }

        constexpr modint &operator--() noexcept {
            val += (val < r) * upperbound;
            val -= r;
            return *this;
        }

        constexpr modint operator+() const noexcept {
            return *this;
        }

        constexpr modint operator-() const noexcept {
            auto t = *this;
            t.set_value(upperbound - this->val);
            return t;
        }

        explicit operator value_type() const noexcept {
            return this->val;
        }

        constexpr modint &operator=(const modint &rhs) & noexcept {
            this->val = rhs.get_raw();
            return *this;
        }

        constexpr modint &operator+=(const modint &rhs) noexcept {
            this->val += rhs.get_raw();
            this->val -= (this->val >= upperbound) * upperbound;
            return *this;
        }

        constexpr modint &operator-=(const modint &rhs) noexcept {
            this->val += upperbound - rhs.get_raw();
            this->val -= (this->val >= upperbound) * upperbound;
            return *this;
        }

        constexpr modint &operator*=(const modint &rhs) noexcept {
            this->val *= rhs.get_raw();
            this->val = reduce(this->val);
            return *this;
        }

        constexpr modint &operator/=(const modint &rhs) noexcept {
            *this = pow(rhs, Mod - 2, *this);
            return *this;
        }

        constexpr modint &operator|=(const modint &rhs) noexcept {
            this->val += rhs.get_raw();
            return *this;
        }

        constexpr void regularize() noexcept {
            this->val %= upperbound;
        }

        constexpr modint operator+(const modint &rhs) noexcept {
            auto t = *this;
            t += rhs;
            return t;
        }

        constexpr modint operator-(const modint &rhs) noexcept {
            auto t = *this;
            t -= rhs;
            return t;
        }

        constexpr modint operator*(const modint &rhs) noexcept {
            auto t = *this;
            t *= rhs;
            return t;
        }

        constexpr modint operator/(const modint &rhs) noexcept {
            auto t = *this;
            t /= rhs;
            return t;
        }
    };

    template<class UnsignedInteger, UnsignedInteger Mod>
    std::ostream& operator<<(std::ostream& os, const modint<UnsignedInteger, Mod>& mint){
        os << mint.get_value();
        return os;
    }
    template<class UnsignedInteger, UnsignedInteger Mod>
    std::istream& operator>>(std::istream& is, modint<UnsignedInteger, Mod>& mint){
        UnsignedInteger t;
        is >> t;
        mint = modint<UnsignedInteger, Mod>(t);
        return is;
    }

    template<typename Field, size_t n>
    class square_matrix {
        using value_type = vector<vector<Field>>;
    public:
        value_type val;

        explicit square_matrix(const value_type &_val) : val(_val) {}

        static value_type e() noexcept {
            value_type ret(n, vector<Field>(n, Field::z()));
            for (size_t i = 0; i < n; ++i)ret[i][i] = Field::e();
            return ret;
        }

        static value_type z() noexcept {
            value_type ret(n, vector<Field>(n, Field::z()));
            return ret;
        }

        static value_type transpose(const value_type &a) noexcept {
            value_type ret(z());
            for (unsigned long i = 0; i != n; ++i)
                for (unsigned long j = 0; j != n; ++j)
                    ret[i][j] = a[j][i];
            return ret;
        }

        square_matrix operator-() const {
            auto ret = this->val;
            for (auto &i : ret) {
                for (auto &j : i)j = -j;
            }
            return square_matrix(ret);
        }

        square_matrix &operator*=(const square_matrix &rhs) noexcept {
            value_type ret(n, vector<Field>(n, Field::z()));
            for(unsigned long i = 0; i != n; ++i)
                for(unsigned long j = 0; j != n; ++j)
                    for(unsigned long k = 0; k != n; ++k)
                        ret[i][j] = ret[i][j] + val[i][k] * rhs.val[k][j];
            this->val = ret;
            return *this;
        }

        vector<Field>& operator[](std::size_t t){
            return val[t];
        }
    };
}

template<typename Monoid>
Monoid pow(Monoid a, size_t n){
    Monoid ret{Monoid::e()};
    while(n){
        if(n & 1)ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}

int main(){
    constexpr long MOD = 1000000007;
    using modint = MMNMM::modint<unsigned long, MOD>;
    size_t k;
    cin >> k;
    k += 1000000013000000042;
    modint N{k % MOD};
    MMNMM::square_matrix<modint, 4> a({{1, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 1, MOD - 1}, {0, 0, 0, 1}});
    auto t = pow(a, k);
    cout << t[0][0] + (t[0][1] + t[0][2] * N) * (N - modint(1)) + t[0][3] << endl;
    return 0;
}

Measured memory_bytes: 256