description: Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.
  
  Define an array b (0 ≤ b_i < k) with n integers. While there exists a pair (i, j) such that b_i ≠ b_j, do the following operation:
  
    * Randomly pick a number i satisfying 0 ≤ i < n. Note that each number i has a probability of 1/n to be picked. 
    * Randomly Pick a number j satisfying 0 ≤ 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 ≤ a_i < k) of n integers. 
  
  For every index i with a_i = -1, replace a_i with a random number j satisfying 0 ≤ 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 p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output the integer equal to p ⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.
  
  After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!
  
  Input
  
  The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^9). 
  
  The second line contains n integers a_1, a_2, …, a_n (-1 ≤ a_i < k).
  
  Output
  
  Output an integer denoting the expected value of f(a) modulo 10^9 + 7.
  
  Examples
  
  Input
  
  
  2 2
  0 1
  
  
  Output
  
  
  2
  
  
  Input
  
  
  2 2
  0 -1
  
  
  Output
  
  
  1
  
  
  Input
  
  
  3 3
  0 1 1
  
  
  Output
  
  
  12
  
  
  Input
  
  
  3 3
  -1 -1 -1
  
  
  Output
  
  
  11
  
  
  Input
  
  
  10 9
  -1 0 -1 1 1 2 2 3 3 3
  
  
  Output
  
  
  652419213
solution: #include <bits/stdc++.h>
  using namespace std;
  const int mod = 1e9 + 7;
  long long inv(long long a) {
    long long u = 0, v = 1, b = mod;
    while (a) {
      long long t = b / a;
      b -= t * a, u -= t * v;
      swap(a, b);
      swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
  }
  struct mint {
    int x;
    mint() : x(0) {}
    mint(int x) : x(x) {}
    mint(long long x) : x() {
      if (x >= mod || x < -mod) x %= mod;
      if (x < 0) x += mod;
      this->x = x;
    }
    mint &operator-=(const mint &rhs) {
      x -= rhs.x;
      if (x < 0) x += mod;
      return *this;
    }
    mint &operator+=(const mint &rhs) {
      x += rhs.x;
      if (x >= mod) x -= mod;
      return *this;
    }
    mint &operator*=(const mint &rhs) {
      x = (long long)x * rhs.x % mod;
      return *this;
    }
    mint &operator/=(const mint &rhs) {
      x = (long long)x * inv(rhs.x) % mod;
      return *this;
    }
    bool operator<(const mint &rhs) { return x < rhs.x; }
    bool operator==(const mint &rhs) { return x == rhs.x; }
    bool operator!=(const mint &rhs) { return x != rhs.x; }
    mint operator-() { return mint(-x); }
    friend mint operator+(const mint &lhs, const mint &rhs) {
      mint ret(lhs);
      return ret += rhs;
    }
    friend mint operator-(const mint &lhs, const mint &rhs) {
      mint ret(lhs);
      return ret -= rhs;
    }
    friend mint operator*(const mint &lhs, const mint &rhs) {
      mint ret(lhs);
      return ret *= rhs;
    }
    friend mint operator/(const mint &lhs, const mint &rhs) {
      mint ret(lhs);
      return ret /= rhs;
    }
    friend ostream &operator<<(ostream &os, const mint &rhs) {
      os << rhs.x;
      return os;
    }
    friend istream &operator>>(istream &is, mint &rhs) {
      long long a;
      is >> a;
      rhs = a;
      return is;
    }
  };
  mint fpow(mint a, long long b) {
    mint r = 1;
    for (; b; b >>= 1) {
      if (b & 1) r = r * a;
      a = a * a;
    }
    return r;
  }
  mint comb(int n, int k) {
    if (n < k || k < 0) return 0;
    static vector<mint> f(1, 1), rf(1, 1);
    if (f.size() <= n) {
      int p = f.size();
      f.resize(n + 1), rf.resize(n + 1);
      for (int i = p; i <= n; ++i) f[i] = f[i - 1] * i;
      rf[n] = 1 / f[n];
      for (int i = n - 1; i >= p; --i) rf[i] = rf[i + 1] * (i + 1);
    }
    return f[n] * rf[k] * rf[n - k];
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<mint> f(n + 1);
    for (int i = 1; i < n; ++i)
      f[i + 1] = (f[i] * i * (k - 1) - 1ll * i * k) / (n - i);
    for (int i = 1; i <= n; ++i) f[i] += f[i - 1];
    map<int, int> cnt;
    vector<int> cnt2(n + 1);
    int c = 0;
    for (int i : a) {
      if (i == -1)
        c += 1;
      else
        cnt[i] += 1;
    }
    for (auto [x, y] : cnt) cnt2[y] += 1;
    cnt2[0] += k - cnt.size();
    vector<int> p;
    for (int i = 0; i <= n; ++i)
      if (cnt2[i]) p.push_back(i);
    mint ans = 0;
    for (int j = 0; j <= c; ++j) {
      mint tmp = comb(c, j) * fpow(k - 1, c - j);
      mint sum = 0;
      for (int i : p) sum += cnt2[i] * f[i + j];
      ans += sum * tmp;
    }
    cout << ans / fpow(k, c) - f[n] << endl;
  }
  