nth Fibo number - MulMatrix

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int mod = 1e9 + 7;
long long n;
struct Matrix
{
    vector<vector<int> > a;
    int row() const
    {
        return a.size();
    }
    int col() const
    {
        return a[0].size();
    }
    auto & operator [] (int i)
    {
        return a[i];
    }
    const auto & operator[] (int i) const
    {
        return a[i];
    }
    Matrix(vector<vector<int> > b)
    {
        a = b;
    }
    Matrix(int r, int c)
    {
        a.resize(r);
        for (int i = 0; i < r; ++ i)
        {
            a[i].resize(c, 0);
        }
    }
    Matrix operator * (const Matrix &v)
    {
        Matrix u = *this;
        Matrix x(u.row(), v.col());
        for (int k = 0; k < u.col(); ++ k)
        {
            for (int i = 0; i < u.row(); ++ i)
            {
                for (int j = 0; j < v.col(); ++ j)
                {
                    x[i][j] = (x[i][j] + 1LL * u[i][k] * v[k][j]) % mod;
                }
            }
        }
        return x;
    }
};
void read()
{
    cin >> n;
}
void solve()
{
    Matrix a({
        {0, 1},
        {1, 1}
    });
    Matrix b({
        {0, 1}
    });
    while(n > 0)
    {
        if (n & 1)
        {
            b = b * a;
        }
        a = a * a;
        n >>= 1;
    }
    cout << b[0][0];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}