tpa pb propusa tema o(logn)

#include <bits/stdc++.h>
using namespace std;
const string FNAME = "data";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
using Matrix2x2 = array<array<int, 2>, 2>;
constexpr int MOD = 1'000'000'007;//'
constexpr Matrix2x2 IDENTITY{{ {1, 0}, {0, 1} }};

Matrix2x2 multiplyMatrices(const Matrix2x2 a, const Matrix2x2 b) {
    Matrix2x2 res;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int sum = 0;
            for (int k = 0; k < 2; k++) {
                sum = (sum + 1LL * a[i][k] * b[k][j] % MOD) % MOD;
            }
            res[i][j] = sum;
        }
    }
    return res;
}

Matrix2x2 toLogPowMatrix(Matrix2x2 base, int exp) {
    Matrix2x2 res = IDENTITY;
    while (exp) {
        if (exp & 1) {
            res = multiplyMatrices(res, base);
        }
        base = multiplyMatrices(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    constexpr Matrix2x2 iniStateMatrix{{ {1, 3}, {0, 0} }};
    constexpr Matrix2x2 transMatrix{{ {0, 2}, {1, 1} }};
    int n;
    fin >> n;
    assert(3 <= n && n <= 1e9);
    Matrix2x2 poweredMatrix = toLogPowMatrix(transMatrix, n - 2);
    Matrix2x2 res = multiplyMatrices(iniStateMatrix, poweredMatrix);
    fout << res[0][1] << endl;
    fout.close();
    return 0;
}