f(0, D) = 1, f(0, A) = f(0, B) = f(0, C) = 0

f(i, D) = f(i - 1, A) + f(i - 1, B) + f(i - 1, C) f(i, A) = f(i - 1, B) + f(i - 1, C) + f(i - 1, D)

but A, B and C points are similar f(i, A) = f(i, B) = f(i, C) therefore f(i, D) = 3 * f(i - 1, A) f(i, A) = 2 * f(i - 1, A) + f(i - 1, D)

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> fD(n + 1), fA(n + 1);
    fD[0] = 1;
    fA[0] = 0;

    for (int i = 1; i <= n; ++i) {
        fD[i] = (3 * fA[i - 1]) % MOD;
        fA[i] = (2 * fA[i - 1] + fD[i - 1]) % MOD;
    }

    cout << fD[n] << endl;
    return 0;
}

These relations can be written in matrix form