Trilogy valid array

#include <bits/stdc++.h> 
using namespace std;

const int MOD = 1e9 + 7;

vector<vector<long long>> matrixMultiply(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
    int n = A.size();
    vector<vector<long long>> res(n, vector<long long>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long sum = 0;
            for (int k = 0; k < n; ++k) {
                sum = (sum + A[i][k] * B[k][j]) % MOD;
            }
            res[i][j] = sum;
        }
    }
    return res;
}

vector<vector<long long>> powerMatrix(const vector<vector<long long>>& base, long long exp) {
    int size = base.size();
    vector<vector<long long>> result(size, vector<long long>(size, 0));

    // Initializing result as identity matrix
    for (int i = 0; i < size; ++i) {
        result[i][i] = 1;
    }

    vector<vector<long long>> baseCopy = base;

    while (exp) {
        if (exp % 2 == 1) {
            result = matrixMultiply(result, baseCopy);
        }
        baseCopy = matrixMultiply(baseCopy, baseCopy);
        exp /= 2;
    }

    return result;
}

int solve(long long A, int B, int C) {
    if (A == 0) return 0;

    vector<long long> initial(B, 0);
    initial[0] = C % MOD;

    vector<vector<long long>> matrix(B, vector<long long>(B, 0));

    for (int i = 0; i < B; ++i) {
        if (i + 1 < B) matrix[i][i + 1] = 1; // Transitioning to the next state
        matrix[i][0] = (C - 1) % MOD;  // Contribution from previous state
    }

    vector<vector<long long>> poweredMatrix = powerMatrix(matrix, A - 1);

    long long totalSum = 0;

    for (int i = 0; i < B; ++i) {
        long long sum = 0;
        for (int j = 0; j < B; ++j) {
            sum = (sum + initial[j] * poweredMatrix[j][i]) % MOD;
        }
        totalSum = (totalSum + sum) % MOD;
    }

    return totalSum;
}

int main() {
    long long A;
    int B, C;
    cin >> A >> B >> C;

    cout << solve(A, B, C) << endl;
    return 0;
}