Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.
Define an array \(b\) (\(0 \leq b_i < k\)) with \(n\) integers. While there exists a pair \((i, j)\) such that \(b_i \ne b_j\), do the following operation:
- Randomly pick a number \(i\) satisfying \(0 \leq i < n\). Note that each number \(i\) has a probability of \(\frac{1}{n}\) to be picked.
- Randomly Pick a number \(j\) satisfying \(0 \leq j < k\).
- Change the value of \(b_i\) to \(j\). It is possible for \(b_i\) to be changed to the same value.
Denote \(f(b)\) as the expected number of operations done to \(b\) until all elements of \(b\) are equal.
You are given two integers \(n\) and \(k\), and an array \(a\) (\(-1 \leq a_i < k\)) of \(n\) integers.
For every index \(i\) with \(a_i = -1\), replace \(a_i\) with a random number \(j\) satisfying \(0 \leq j < k\). Let \(c\) be the number of occurrences of \(-1\) in \(a\). There are \(k^c\) possibilites of \(a\) after the replacement, each with equal probability of being the final array.
Find the expected value of \(f(a)\) modulo \(10^9 + 7\).
Formally, let \(M = 10^9 + 7\). It can be shown that the answer can be expressed as an irreducible fraction \(\frac{p}{q}\), where \(p\) and \(q\) are integers and \(q \not \equiv 0 \pmod{M}\). Output the integer equal to \(p \cdot q^{-1} \bmod M\). In other words, output such an integer \(x\) that \(0 \le x < M\) and \(x \cdot q \equiv p \pmod{M}\).
After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!