Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % mod; }
int sub(int x, int y) { return (x - y + mod) % mod; }
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int modpow(int n, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = mul(res, n);
        n = mul(n, n);
        k >>= 1;
    }
    return res;
}
int divide(int a, int b) { return mul(a, modpow(b, mod - 2)); }

vector<vector<int>> mul(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    int n = a.size(), m = b[0].size();
    vector<vector<int>> c(n, vector<int>(m));
    int r = a[0].size();
    assert(r == (int)b.size());

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < r; k++)
                c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));

    return c;
}

void solve() {
    ll n;
    cin >> n;

    vector<vector<int>> mat(5, vector<int>(5));
    for (int i = 0; i < 4; i++)
        for (int k = 0; k < 4; k++) if (k != i) mat[i][k] = 1;
    mat[4][3] = mat[4][4] = 1;

    vector<vector<int>> a(5, vector<int>(5));
    for (int i = 0; i < 5; i++) a[i][i] = 1;

    vector<vector<int>> fin(5, vector<int>(1));
    fin[3][0] = 1;
    n += 1;
    while (n) {
        if (n & 1) a = mul(a, mat);
        mat = mul(mat, mat);
        n >>= 1;
    }
    a = mul(a, fin);
    cout << sub(a[4][0], 1) << "\n";   
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    tt = 1, tc = 1; // cin >> tt;
    while (tt--) solve(), tc++;
}