Chanek 先生打开了一封来自他目前在 Singanesia 学习的同事的来信。这是它所说的。
用 $$$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$$$ 执行的预期操作数,直到 $$$b$$$ 的所有元素都相等。
给定两个整数 $$$n$$$ 和 $$$k$$$,以及一个由 $$$n$$$ 整数组成的数组 $$$a$$$ ($$$-1 \leq a_i < k$$$)。
对于 $$$a_i = -1$$$ 的每个索引 $$$i$$$,将 $$$a_i$$$ 替换为满足 $$$0 \leq j < k$$$ 的随机数 $$$j$$$。令$$$c$$$ 为$$$-1$$$ 在$$$a$$$ 中出现的次数。替换后有 $$$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$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
读完信后,查内克先生把任务交给了你。为了他们的友谊,解决这个问题!
输入
第一行包含两个整数 $$$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 < k$$$)。
输出
输出一个整数,表示 $$$f(a)$$$ 模 $$$10^9 + 7$$$ 的期望值。
示例
输入 #1
2 2 0 1
输出 #1
2
输入 #2
2 2 0 -1
输出 #2
1
输入 #3
3 3 0 1 1
输出 #3
12
输入#4
3 3 -1 -1 -1
输出#4
11
输入 #5
10 9 -1 0 -1 1 1 2 2 3 3 3
输出 #5
652419213