Leetcode 3339. Find the Number of K-Even Arrays

Count how many length-n arrays with elements in [1..m] have exactly k prefixes whose prefix sum is even (i.e., the prefix sum parity is even at exactly k positions), returning the answer modulo 10^9+7. The core challenge is modeling parity transitions and using combinatorics/DP to count possibilities efficiently for large n and m.