CF1575F.Finding Expected Value

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 \lt 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 \lt 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 \lt 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 \lt k$) of $n$ integers.

For every index $i$ with $a_i = -1$, replace $a_i$ with a random number $j$ satisfying $0 \leq j \lt 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 \lt 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!

陈克先生收到了一封来自他朋友的信，这位朋友目前正在新迦尼西亚学习。信的内容如下：

定义一个长度为 $n$ 的数组 $b$（满足 $0 \leq b_i < k$）。当数组中存在一对下标 $(i, j)$ 使得 $b_i \ne b_j$ 时，重复执行以下操作：

• 随机选取一个下标 $i$，满足 $0 \leq i < n$。注意：每个下标 $i$ 被选中的概率均为 $\frac{1}{n}$；
• 随机选取一个整数 $j$，满足 $0 \leq j < k$；
• 将 $b_i$ 的值修改为 $j$。注意：$b_i$ 可能被修改为它原来的值。

记 $f(b)$ 为将数组 $b$ 所有元素变为相等所需的操作次数的期望值。

现给定两个整数 $n$ 和 $k$，以及一个长度为 $n$ 的数组 $a$（满足 $-1 \leq a_i < k$）。

对每个满足 $a_i = -1$ 的下标 $i$，将其替换为一个在 $[0, k)$ 范围内均匀随机选取的整数 $j$。设 $c$ 为数组 $a$ 中 $-1$ 的出现次数，则替换后共有 $k^c$ 种可能的数组 $a$，每种结果出现的概率均等。

求 $f(a)$ 的期望值对 $10^9 + 7$ 取模的结果。

形式化地，令 $M = 10^9 + 7$。可以证明该答案可表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 均为整数，且 $q \not\equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的唯一整数 $x$。

读完这封信后，陈克先生把这个任务交给了你。为了维护他们之间的友谊，请解决这个问题！

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $2 \leq k \leq 10^9$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \lt k$).

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$2 \leq k \leq 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \leq a_i \lt k$）。

Output an integer denoting the expected value of $f(a)$ modulo $10^9 + 7$.

输出一个整数，表示 $f(a)$ 的期望值对 $10^9 + 7$ 取模的结果。