[Gym] RGB plants

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : RGB plants
Source            : Codeforces Gym
Category          : Linear Algebra
Algorithm         : Matrix Exponentiation
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll                long long
#define memo(a, b)        memset(a, b, sizeof a)
#define For(a, c)         for (auto a = 0; a < c; a++)
#define FOR(a, c)         for (auto a = 1; a <= c; a++)
 
inline int read()         { int a; scanf("%d", &a); return a; }
inline ll readLL()        { ll a; scanf("%lld", &a); return a; }
 
static const ll mod = 1000000007;
 
struct Mat
{
    int row, col;
    ll v[4][4];
 
    void init(int row = 0, int col = 0)
    {
        this->row = row;
        this->col = col;
        int c = 0;
        For(i, row) For(j,  col) this->v[i][j] = ++c;
    }
    Mat multiply(const Mat &A, const Mat &B)
    {
        Mat ret;
        ret.row = A.row;
        ret.col = B.col;
        For(i, ret.row)
        {
            For(j, ret.col)
            {
                ll sum = 0;
                For(k, A.col)
                {
                    sum += (A.v[i][k]%mod * B.v[k][j]%mod)%mod;
                    sum %= mod;
                }
                ret.v[i][j] = sum;
            }
        }
        return ret;
    }
    Mat modPow(Mat mat, ll p)
    {
        if (p == 1) return mat;
        if (p&1) return mat.multiply(mat, modPow(mat, p-1));
        Mat ret = modPow(mat, p>>1);
        return ret.multiply(ret, ret);
    }
    ll getRes()
    {
        ll sum = 0;
        For(i, row) For(j, col) sum = (sum + v[i][j])%mod;
        return sum%mod;
    }
};
 
int main()
{
    int tc = read();
    For(tcase, tc)
    {
        ll n = readLL();
        if (n == 1)
        {
            puts("3");
            continue;
        }
        Mat mat;
        mat.init(3, 3);
        mat = mat.modPow(mat, n-1);
        ll ans = mat.getRes();
        printf("%lld\n", ans);
    }
}