3339. Find the Number of K-Even Arrays

You are given three integers n, m, and k.

An array arr is called k-even if there are exactly k indices such that, for each of these indices i (0 <= i < n - 1):

• (arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] is even.

Return the number of possible k-even arrays of size n where all elements are in the range [1, m].

Since the answer may be very large, return it modulo 109 + 7.