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: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.util.Arrays;
  import java.io.BufferedWriter;
  import java.io.Writer;
  import java.io.OutputStreamWriter;
  import java.util.HashMap;
  import java.util.InputMismatchException;
  import java.io.IOException;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader in = new InputReader(inputStream);
          OutputWriter out = new OutputWriter(outputStream);
          FFindingExpectedValue solver = new FFindingExpectedValue();
          solver.solve(1, in, out);
          out.close();
      }
  
      static class FFindingExpectedValue {
          MOD mod = new MOD();
  
          public void solve(int testNumber, InputReader in, OutputWriter out) {
              int n = in.nextInt(), k = in.nextInt();
              int[] f = new int[n + 1];
              f[1] = 1000000006;
              int d = f[1];
              for (int a = 1; a < n; a++) {
                  d = mod.subtract(mod.multiply(mod.multiply(d, a), k - 1), n);
                  d = mod.multiply(d, mod.inverse(n - a));
                  f[a + 1] = mod.add(f[a], d);
              }
              HashMap<Integer, Integer> hm = new HashMap<>();
              for (int i = 0; i < n; i++) {
                  int u = in.nextInt();
                  hm.put(u, hm.getOrDefault(u, 0) + 1);
              }
              int init = 0, fin = f[n];
              int t = hm.getOrDefault(-1, 0);
              int[] c = new int[t + 1];
              int h = mod.power(mod.subtract(1, mod.inverse(k)), t);
              int r = mod.inverse(k - 1);
              int R = 1, C = 1;
              for (int i = 0; i <= t; i++) {
                  c[i] = mod.multiply(R, C);
                  R = mod.multiply(R, r);
                  C = mod.multiply(C, t - i);
                  C = mod.multiply(C, mod.inverse(i + 1));
              }
              hm.remove(-1);
              int[] answers = new int[n + 1];
              Arrays.fill(answers, -1);
  
              for (int b : hm.keySet()) {
                  int a = hm.get(b);
                  if (answers[a] == -1) {
                      answers[a] = 0;
                      for (int i = 0; i <= t; i++) {
                          answers[a] = mod.add(answers[a], mod.multiply(c[i], f[a + i]));
                      }
                  }
                  init = mod.add(init, answers[a]);
              }
              int x = 0;
              for (int i = 0; i <= t; i++) {
                  x = mod.add(x, mod.multiply(c[i], f[i]));
              }
              init = mod.add(init, mod.multiply(k - hm.size(), x));
              out.println(mod.subtract(mod.multiply(init, h), fin));
          }
  
      }
  
      static class MOD {
          static final int modulo = 1000000007;
  
          public int add(int x, int y) {
              x += y;
              if (x >= modulo) x -= modulo;
              return x;
          }
  
          public int subtract(int x, int y) {
              x -= y;
              if (x < 0) x += modulo;
              return x;
          }
  
          public int multiply(int x, int y) {
              return (int) ((x * 1L * y) % modulo);
          }
  
          public int power(int x, long y) {
              int ans = 1;
              for (; y > 0; y >>= 1, x = (int) ((x * 1L * x) % modulo))
                  if (y % 2 == 1) ans = (int) ((ans * 1L * x) % modulo);
              return ans;
          }
  
          public int inverse(int x) {
              return power(x, modulo - 2);
          }
  
      }
  
      static class OutputWriter {
          private final PrintWriter writer;
  
          public OutputWriter(OutputStream outputStream) {
              writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
          }
  
          public OutputWriter(Writer writer) {
              this.writer = new PrintWriter(writer);
          }
  
          public void println(Object... objects) {
              for (int i = 0; i < objects.length; i++) {
                  if (i != 0) {
                      writer.print(' ');
                  }
                  writer.print(objects[i]);
              }
              writer.print('\n');
          }
  
          public void close() {
              writer.close();
          }
  
      }
  
      static class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private InputReader.SpaceCharFilter filter;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          public int read() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar++];
          }
  
          public int nextInt() {
              int c = read();
              while (isSpaceChar(c)) c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null) {
                  return filter.isSpaceChar(c);
              }
              return isWhitespace(c);
          }
  
          public static boolean isWhitespace(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
  
          }
  
      }
  }
  
  