Count the Number of Arrays with K Matching Adjacent Elements
<p>You are given three integers <code>n</code>, <code>m</code>, <code>k</code>. A <strong>good array</strong> <code>arr</code> of size <code>n</code> is defined as follows:</p>

<ul>
	<li>Each element in <code>arr</code> is in the <strong>inclusive</strong> range <code>[1, m]</code>.</li>
	<li><em>Exactly</em> <code>k</code> indices <code>i</code> (where <code>1 &lt;= i &lt; n</code>) satisfy the condition <code>arr[i - 1] == arr[i]</code>.</li>
</ul>

<p>Return the number of <strong>good arrays</strong> that can be formed.</p>

<p>Since the answer may be very large, return it <strong>modulo </strong><code>10<sup>9 </sup>+ 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3, m = 2, k = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>There are 4 good arrays. They are <code>[1, 1, 2]</code>, <code>[1, 2, 2]</code>, <code>[2, 1, 1]</code> and <code>[2, 2, 1]</code>.</li>
	<li>Hence, the answer is 4.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4, m = 2, k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>The good arrays are <code>[1, 1, 1, 2]</code>, <code>[1, 1, 2, 2]</code>, <code>[1, 2, 2, 2]</code>, <code>[2, 1, 1, 1]</code>, <code>[2, 2, 1, 1]</code> and <code>[2, 2, 2, 1]</code>.</li>
	<li>Hence, the answer is 6.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, m = 2, k = 0</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>The good arrays are <code>[1, 2, 1, 2, 1]</code> and <code>[2, 1, 2, 1, 2]</code>. Hence, the answer is 2.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= k &lt;= n - 1</code></li>
</ul>
Math; Combinatorics
impl Solution {
    pub fn count_good_arrays(n: i32, m: i32, k: i32) -> i32 {
        const N: usize = 1e5 as usize + 10;
        const MOD: i64 = 1_000_000_007;
        use std::sync::OnceLock;

        static F: OnceLock<Vec<i64>> = OnceLock::new();
        static G: OnceLock<Vec<i64>> = OnceLock::new();

        fn qpow(mut a: i64, mut k: i64, m: i64) -> i64 {
            let mut res = 1;
            while k != 0 {
                if k & 1 == 1 {
                    res = res * a % m;
                }
                a = a * a % m;
                k >>= 1;
            }
            res
        }

        fn init() -> (&'static Vec<i64>, &'static Vec<i64>) {
            F.get_or_init(|| {
                let mut f = vec![1i64; N];
                for i in 1..N {
                    f[i] = f[i - 1] * i as i64 % MOD;
                }
                f
            });

            G.get_or_init(|| {
                let f = F.get().unwrap();
                let mut g = vec![1i64; N];
                for i in 1..N {
                    g[i] = qpow(f[i], MOD - 2, MOD);
                }
                g
            });

            (F.get().unwrap(), G.get().unwrap())
        }

        fn comb(f: &[i64], g: &[i64], m: usize, n: usize) -> i64 {
            f[m] * g[n] % MOD * g[m - n] % MOD
        }

        let (f, g) = init();
        let n = n as usize;
        let m = m as i64;
        let k = k as usize;

        let c = comb(f, g, n - 1, k);
        let pow = qpow(m - 1, (n - 1 - k) as i64, MOD);
        (c * m % MOD * pow % MOD) as i32
    }
}
