Count the Number of Arrays with K Matching Adjacent Elements | Leetcode 3405

class Solution {
    using ll = long long;
    int MOD = 1e9+7;
    vector<int> fact,inv_fact;

    int binaryExp(ll a,ll b){
        ll res = 1;
        while(b){
            if(b&1)
                res = (res*a)%MOD;
            a = (a*a)%MOD;
            b /= 2;
        }
        return res;
    }
    int MMI(int val){
        return binaryExp(val,MOD-2);
    }
    void inverseFact(const int& n){
        inv_fact = vector<int>(n+1);
        inv_fact[n] = MMI(fact[n]);
        for(int i=n;i>0;--i)
            inv_fact[i-1] = (1LL*inv_fact[i]*i)%MOD;
    }
    void factorial(const int& n){
        fact = vector<int>(n+1);
        fact[0] = 1;
        for(int i=1;i<=n;++i)
            fact[i] = (1LL*i*fact[i-1])%MOD;
    }
    void precompute(const int& n){
        factorial(n);
        inverseFact(n);
    }
public:
    int countGoodArrays(int n, int m, int k) {
        precompute(n);

        int run_ways = ((1LL * fact[n-1] * inv_fact[n-k-1])%MOD * inv_fact[k])%MOD;
        int ways_to_assign = (1LL * m * binaryExp(m-1,n-k-1))%MOD;
        return (1LL * run_ways * ways_to_assign)%MOD;
    }
};
/*
//JAVA
import java.util.Arrays;

public class Solution {
    private static final int MOD = (int)1e9 + 7;
    private int[] fact;
    private int[] invFact;

    private int binaryExp(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }
        return (int)res;
    }

    private int mmi(int val) {
        return binaryExp(val, MOD - 2);
    }

    private void inverseFact(int n) {
        invFact = new int[n + 1];
        invFact[n] = mmi(fact[n]);
        for (int i = n; i > 0; i--) {
            invFact[i - 1] = (int)((1L * invFact[i] * i) % MOD);
        }
    }

    private void factorial(int n) {
        fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (int)((1L * i * fact[i - 1]) % MOD);
        }
    }

    private void precompute(int n) {
        factorial(n);
        inverseFact(n);
    }

    public int countGoodArrays(int n, int m, int k) {
        precompute(n);

        int runWays = (int)((1L * fact[n - 1] * invFact[n - k - 1] % MOD * invFact[k]) % MOD);
        int waysToAssign = (int)(1L * m * binaryExp(m - 1, n - k - 1) % MOD);
        return (int)(1L * runWays * waysToAssign % MOD);
    }
}

#Python
MOD = 10**9 + 7

class Solution:
    def __init__(self):
        self.fact = None
        self.inv_fact = None

    def binary_exp(self, a, b):
        res = 1
        a = a % MOD
        while b > 0:
            if b & 1:
                res = (res * a) % MOD
            a = (a * a) % MOD
            b >>= 1
        return res

    def mmi(self, val):
        return self.binary_exp(val, MOD - 2)

    def inverse_fact(self, n):
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = self.mmi(self.fact[n])
        for i in range(n, 0, -1):
            self.inv_fact[i - 1] = (self.inv_fact[i] * i) % MOD

    def factorial(self, n):
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % MOD

    def precompute(self, n):
        self.factorial(n)
        self.inverse_fact(n)

    def count_good_arrays(self, n, m, k):
        self.precompute(n)

        run_ways = (self.fact[n - 1] * self.inv_fact[n - k - 1] % MOD) * self.inv_fact[k] % MOD
        ways_to_assign = m * self.binary_exp(m - 1, n - k - 1) % MOD
        return run_ways * ways_to_assign % MOD
*/