Tính nhanh Fibo bằng Ma trận

#include <bits/stdc++.h>

using namespace std;

const long long mod = (long long)(1e9 + 7);

typedef vector<vector<long long>> Matrix;

Matrix m = {{1, 1}, {1, 0}};

Matrix nhan(Matrix a, Matrix b)
{
    Matrix res = {{0, 0}, {0, 0}};
    res[0][0] = ((a[0][0] * b[0][0]) % mod + (a[0][1] * b[1][0] ) % mod ) % mod;
    res[0][1] = ((a[0][0] * b[1][0]) % mod + (a[0][1] * b[1][1]) % mod) % mod;
    res[1][0] = ((a[1][0] * b[0][0]) % mod + (a[1][1] * b[1][0]) % mod) % mod;
    res[1][1] = ((a[1][0] * b[1][0]) % mod + (a[1][1] * b[1][1]) % mod) % mod;

    return res;
}

Matrix Power(Matrix x, int n)
{
    if (n == 0) return {{1, 0}, {0, 1}};
    Matrix t = Power(x, n / 2);
    t = nhan(t, t);

    if (n % 2 == 0) return t;
    return nhan(t, x);
}

int main()
{

    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    Matrix res = Power(m, n);
    cout << res[1][0] << '\n';

    return 0;
}