fuho.cpp

#include<iostream>
#include<cstdlib>
#include<vector>

#define long long long
#define nln '\n'
#define matrix vector<vector<long>>

using namespace std;

const long MOD = 1e9+7;

matrix operator*(const matrix &a, const matrix &b)
{
    matrix c(a.size());
    for (long i = 0; i < (long)a.size(); ++i){
        c[i].resize(b[0].size(), 0);
        for (long j = 0; j < (long)b[0].size(); ++j)
            for (long k = 0; k < (long)a[0].size(); ++k)
                c[i][j] += a[i][k]*b[k][j], c[i][j] %= MOD;
    }
    return c;
}

matrix binpow(const matrix &a, long n)
{
    if (n == 0)
        return (matrix){{1, 0}, {0, 1}};
    if (n == 1)
        return a;
    matrix tem = binpow(a, n/2);
    if (n % 2 == 1)
        return tem*tem*a;
    return tem*tem;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    freopen("fuho.inp", "r", stdin);
    freopen("fuho.out", "w", stdout);
    matrix a{{1, 1}, {2, 0}};
    matrix b{{3}, {2}};
    long n;
    cin >> n;
    while (n--){
        long i;
        cin >> i;
        if (i > 1){
            cout << (binpow(a, i-2)*b)[0][0] << nln;
            continue;
        }
        if (i == 1){
            cout << 1 << nln;
            continue;
        }
        if (i == 0){
            cout << 0 << nln;
            continue;
        }
    }
    return 0;
}