Untitled

#include <bits/stdc++.h>

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define All(v) (v).begin(), (v).end()
#define rAll(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el "\n"
#define Chris_ signed main()
#define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef set<int> sii;
typedef map<int, int> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;

const int mod = (int) 1e9 + 7;
const int INF = (int) 1e5;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll n, t;

struct matrix
{
    ll x[2][2];
    matrix() // constructor
    {
        memset(x, 0, sizeof x);
    }
};

matrix operator * (const matrix &a, const matrix &b)
{
    matrix c;
    FOR(i, 0, 2)
    {
        FOR(j, 0, 2)
        {
            FOR(k, 0, 2)
            {
                c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j] % mod) % mod;
            }
        }
    }
    return c;
}

matrix Pow(matrix t, ll n)
{
    matrix res;
    FOR(i, 0, 2) res.x[i][i] = 1;
    while(n)
    {
        if(n % 2) res = res * t;
        t = t * t;
        n /= 2;
    }
    return res;
}

void solve()
{
    matrix a;
    cin >> n;
    if(n == 1)
    {
        cout << 1 << el;
        return;
    }
    if(n == 2)
    {
        cout << 3 << el;
        return;
    }
    matrix t;
    t.x[0][0] = 1;
    t.x[0][1] = 2;
    t.x[1][0] = 1;
    t.x[1][1] = 0;
    t = Pow(t, n - 2);
    ll f2 = 3;
    ll f1 = 1;
    ll fn = (t.x[0][0] * f2 % mod + t.x[0][1] * f1 % mod) % mod;
    cout << fn << el;
}

Chris_
{
    faster
    file(Chris)

    cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}