Untitled

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    ll dp[n + 1][10] = {};
    
    for (int k = 1; k <= 9; ++k) {
        if (k != 8) {
            dp[1][k] = 1;
        }
    }
    
    vector<vector<int>> g(10);
    g = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
    
    for (int len = 2; len <= n; ++len) {
        for (int k = 0; k <= 9; ++k) {
            for (int x: g[k]) {
                dp[len][k] = (dp[len][k] + dp[len - 1][x]) % mod;
            }
        }
    }
    
    ll ans = 0;
    for (int k = 0; k <= 9; ++k) {
        ans = (ans + dp[n][k]) % mod;
    }
    
    cout << ans;
    return 0;    
}