[CSES] Counting Towers

vector<vll> matrixmul(vector<vll> v1, vector<vll> v2)
{
    ll n = v1.size();

    vector<vll> a;

    for (ll i = 0; i < n; i++)
    {
        vll x;
        for (ll j = 0; j < n; j++)
        {
            ll val = 0;
            for (ll k = 0; k < n; k++)
            {
                val += v1[i][k] * v2[k][j];
                val %= mod;
            }
            x.pb(val);
        }
        a.pb(x);
    }

    return a;
}
vector<vll> matrixpow(vector<vll> v, ll ex)
{
    if (ex == 1)
        return v;
    else
    {
        vector<vll> temp = matrixpow(v, ex / 2);
        vector<vll> mul = matrixmul(temp, temp);
        if (ex & 1)
            return matrixmul(mul, v);
        else
            return mul;
    }
}

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

    // vvll dp(n + 1, vll(2, 0));
    // // dp[i][j] : ith block has block type j
    // // j = 0: single block, j = 1: two blocks
    // dp[0][0] = dp[0][1] = 1;

    if (n == 1)
    {
        cout << 2 << "\n";
        return;
    }

    vvll matrix = {{2, 1}, {1, 4}};
    vvll ans = matrixpow(matrix, n - 1);
    debug(ans);
    vvll start = {{1, 0}, {1, 0}};
    ans = matrixmul(ans, start);
    cout << (ans[0][0] + ans[1][0]) % mod << "\n";

    // FOR(i, 1, n - 1)
    // {
    //     dp[i][0] = 2 * dp[i - 1][0] + dp[i - 1][1];
    //     dp[i][1] = 4 * dp[i - 1][1] + dp[i - 1][0];

    //     dp[i][0] %= mod, dp[i][1] %= mod;
    // }

    // cout << (dp[n - 1][0] + dp[n - 1][1]) % mod << "\n";
}