Revise paste Untitled

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
typedef vector<vector<double>> d_matrix;
const int maxn = 1e5 + 10;
const int INF = 2e9;
const ll MOD = 100000007;

class StairsToRazorTower
{
public:
    matrix multiply_two_matrices(matrix A, matrix B) {
        int n_a = (int) A.size(), m_a = (int) A[0].size();
        int n_b = (int) B.size(), m_b = (int) B[0].size();
        
        if(m_a != n_b) {
            return {{0}};
        }
        matrix res(n_a, vector<ll>(m_b, 0));
        for(int i = 0; i < n_a; i++) {
            for(int j = 0; j < m_b; j++) {
                ll c = 0;
                for(int k = 0; k < n_a; k++) {
                    c += (A[i][k] * B[k][j]) % MOD;
                    c %= MOD;
                }
                res[i][j] = c % MOD;
            }
        }
        
        return res;
    }
    ll nth_fibbonaci_number(ll x) {
        matrix A = {
            {1, 0, 1},
            {1, 0, 0},
            {0, 1, 0}
        };
        matrix B = A;
    //    for(int i = 0; i < x; i++) {
    //        A = multiply_two_matrices(A, B);
    //    }
        matrix res = {
            {1, 0, 0,},
            {0, 1, 0},
            {0, 0, 1}
        };
        while(x) {
            if(x % 2 == 1) {
                res = multiply_two_matrices(res, A);
            }
            A = multiply_two_matrices(A, A);
            x /= 2;
        }
        
        return res[0][0];
    }
    ll getNumberOfWays( ll n )
    {
        return nth_fibbonaci_number(n);
    }
};
int main() {
//    nth_fibbonaci_number(8);
//    return 0;
    StairsToRazorTower s;
    
    for(int i = 1; i <= 10; i++) {
        cout << s.getNumberOfWays(969710026) << " ";
    }
    return 0;
}