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 < 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!

输入输出格式

输入格式

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 < k $ ).

输出格式

Output an integer denoting the expected value of $ f(a) $ modulo $ 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

暂时还没有翻译