12849.cpp

#include <iostream>
#define ll long long
using namespace std;

const int MOD = 1000000007;

ll ans[8][8] = {{0, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0},
                {0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 1, 1, 0, 1, 1},
                {0, 0, 0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 1, 0}};

ll arr[8][8] = {{0, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 0},
                {0, 0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 1, 1, 0, 1, 1},
                {0, 0, 0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 1, 0}};

void solve() {
    ll tmp[8][8] = {
        0,
    };
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            for (int k = 0; k < 8; k++) {
                tmp[i][j] += (ans[i][k] * arr[k][j]);
            }
        }
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            ans[i][j] = tmp[i][j] % MOD;
        }
    }
}

int main() {
    int d;
    cin >> d;
    for (int i = 1; i < d; i++) {
        solve();
    }
    cout << ans[7][7] << "\n";
}