HackerRank - walmartLabs - Fibonacci sum - study code II

FibonacciSum_studyCode2B.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static long M = 1000000007;
        static long[,] M_I = new long[,] { { 1, 0 }, { 0, 1 } };
        static long[,] M_F = new long[,] { { 0, 1 }, { 1, 1 } };

        static long[,] Mul(long[,] A, long[,] B)
        {
            long[,] C = new long[2, 2];
            for (int i = 0; i < 2; i++)
                for (int k = 0; k < 2; k++)
                    for (int j = 0; j < 2; j++)
                        C[i, k] = (C[i, k] + A[i, j] * B[j, k]) % M;
            return C;
        }
        static long[,] Add(long[,] A, long[,] B)
        {
            long[,] C = new long[2, 2];
            for (int i = 0; i < 2; i++)
                for (int k = 0; k < 2; k++)
                    C[i, k] = (A[i, k] + B[i, k]) % M;
            return C;
        }
        static long[,] Pow(long[,] A, int p)
        {
            if (p == 1)
                return A;
            if (p % 2 == 1)
                return Mul(A, Pow(A, p - 1));
            long[,] X = Pow(A, p / 2);
            return Mul(X, X);
        }
        static long ExtrFib(long[,] A)
        {
            return (A[0, 0] + A[0, 1]) % M;
        }
        static long[,] FibMat(int n)
        {
            if (n == 1)
                return M_I;
            return Pow(M_F, n - 1);
        }

    static void Main(String[] args) {
        int q = int.Parse(Console.ReadLine());
            for (int test = 0; test < q; test++)
            {
                int n = int.Parse(Console.ReadLine());
                int[] a = Console.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
                var b = a.Select(FibMat).ToArray();
                var c = b.Select(l => Mul(l, M_F)).ToArray();
                long tot = 0;
                var G = M_I;
                for (int k = n - 1; k >= 0; k -= 1)
                {
                    var P = Mul(b[k], G);
                    tot = (tot + ExtrFib(P)) % M;
                    G = Mul(c[k], G);
                    G = Add(M_I, G);
                }
                Console.WriteLine(tot);
            }
    }
}