Find Nth Fibonacci

• Time : O(logn)
• Space : O(1)

const long long mod = 1e9+7;

vector<vector<long long>> mul(vector<vector<long long>> A, vector<vector<long long>> B) {
    vector<vector<long long>> C(A.size(), vector<long long>(B[0].size(), 0));
    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B[0].size(); j++)
            for (int k = 0; k < A[0].size(); k++) {
                C[i][j] += (A[i][k] * B[k][j]) % mod;
                C[i][j] %= mod;
            }
    return C;
}

vector<vector<long long>> pow(vector<vector<long long>> A, int n) {
    if (n == 0) return vector<vector<long long>>(A.size(), vector<long long>(A[0].size(), 1));
    if (n == 1) return A;
    if (n == 2) return mul(A, A);
    if (n & 1) return mul(pow(pow(A, n/2), 2), A);
    return pow(pow(A, n/2), 2);
}

int Solution::solve(int A) {
    if (A == 1 || A == 2) return 1;
    return mul(pow({{1, 1}, {1, 0}}, A-2), {{1}, {1}})[0][0];
}