#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

template <typename T, std::size_t n>
ostream& operator<<(ostream& os, const array<T, n>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

constexpr int N = 31;

struct Vec {
    Vec()
    {
        for (int i = 0; i < N; i++) {
            table[i] = 0;
        }
    }

    Vec(const string& s)
    {
        assert(s.size() == N);
        for (int i = 0; i < N; i++) {
            table[i] = s[i] - '0';
        }
    }
    ll operator*(const Vec& vec) const
    {
        ll ans = 0;
        for (int i = 0; i < N; i++) {
            ans += table[i] * vec.table[i];
            ans %= MOD;
        }
        return ans;
    }

    array<ll, N> table;
};

struct Matrix {
    Matrix()
    {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                table[i][j] = 0;
            }
        }
    }

    Matrix(const array<string, N>& s)
    {
        for (int i = 0; i < N; i++) {
            assert(s[i].size() == N);
            for (int j = 0; j < N; j++) {
                table[i][j] = s[i][j] - '0';
            }
        }
    }

    static Matrix Unit()
    {
        Matrix ans;
        for (int i = 0; i < N; i++) {
            ans.table[i][i] = 1;
        }
        return ans;
    }

    Matrix operator*(const Matrix& mat) const
    {
        Matrix ans;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    ans.table[i][j] += table[i][k] * mat.table[k][j];
                    ans.table[i][j] %= MOD;
                }
            }
        }
        return ans;
    }

    array<array<ll, N>, N> table;
};

inline Vec operator*(const Vec& vec, const Matrix& mat)
{
    Vec ans;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans.table[i] += mat.table[j][i] * vec.table[j];
            ans.table[i] %= MOD;
        }
    }
    return ans;
}

Matrix power(const Matrix& mat, const ll n)
{
    if (n == 0) {
        return Matrix::Unit();
    }
    if (n % 2 == 1) {
        return mat * power(mat, n - 1);
    } else {
        const Matrix pp = power(mat, n / 2);
        return pp * pp;
    }
}

int main()
{

    cin.tie(0);
    ios::sync_with_stdio(false);

    const array<string, N> trans{{
        //0123456789012345678901234567890
        "0000000000000000000010000000001",
        "0000000010000010000000000100001",
        "0000000000000000000010000100001",
        "0000000000000010000010000000001",
        "0000000010000010000010000100001",
        "0000000000000000001000000010100",
        "0000000001000000000000000010000",
        "0000000001000000001000000010100",
        "0000000000000000000001000000000",
        "0000000000000000010001000000100",
        "0000010000000000000001000001000",
        "1000010000001000010001100001010",
        "0000000000000000000100000000001",
        "0010000000000010000100001000001",
        "0000000000000000000100000000001",
        "0010000000000010000100001000001",
        "0010000000000010000100001000001",
        "0000001000000000100000000000100",
        "0000000000100000100000000000000",
        "0000001000100000100000000000100",
        "0000000000010000000000000000000",
        "0100000000010100000000010000000",
        "0000000100000000000000000000001",
        "0001000100000001000000000100001",
        "0001000100000001000000000100001",
        "0000000100000000000000000000001",
        "0001000100000001000000000100001",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
    }};
    //0123456789012345678901234567890
    const string init = "0011000110000021000110001200003";
    const string proper = "0000000000010101100001011011111";

    const Matrix mat(trans);
    const Vec initial(init);
    const Vec last(proper);
    ll n;
    cin >> n;
    if (n == 1) {
        cout << 2 << endl;
    } else {
        const Vec ans = initial * power(mat, n - 2);
        show(ans.table);
        cout << ans * last << endl;
    }

    return 0;
}