#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 1e9 + 7;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
const int N = 1e5 + 5;
int a[N], f[N], fac[N], inv[N], t[N], tt[N], pw[N];
int n, k, ans;
inline int C(int n, int m) {
  if (n < m || m < 0) return 0;
  return mul(fac[n], mul(inv[m], inv[n - m]));
}
int main() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
  inv[N - 1] = fpow(fac[N - 1], md - 2);
  for (int i = N - 1; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
  read(n);
  read(k);
  pw[0] = 1;
  for (int i = 1; i <= n; i++) pw[i] = mul(pw[i - 1], k - 1);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 0; i < n; i++) {
    int tem = fpow(n - i, md - 2);
    int c2 = mul(sub(0, mul(i, k - 1)), tem);
    int c1 = mul(sub(mul(n, k), add(i, mul(n - i, k - 1))), tem);
    int c0 = mul(sub(0, mul(k, i)), tem);
    f[i + 1] = add(c0, mul(c1, f[i]));
    if (i != 0) f[i + 1] = add(f[i + 1], mul(c2, f[i - 1]));
  }
  sort(a + 1, a + n + 1);
  int cnt = 0;
  t[0] = k;
  for (int l = 1, r; l <= n; l = r + 1) {
    r = l;
    while (r < n && a[r + 1] == a[l]) ++r;
    if (a[l] == -1) {
      cnt = r - l + 1;
      continue;
    }
    ++t[r - l + 1];
    --t[0];
  }
  for (int i = 0; i <= n; i++) {
    if (t[i]) {
      for (int j = 0; j <= cnt; j++) {
        tt[i + j] = add(tt[i + j], mul(t[i], mul(C(cnt, j), pw[cnt - j])));
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    ans = add(ans, mul(tt[i], f[i]));
  }
  ans = mul(ans, fpow(fpow(k, cnt), md - 2));
  print(sub(ans, f[n]), '\n');
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) {
  f = 0;
  T fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      fu = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  f *= fu;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x < 10)
    putchar(x + 48);
  else
    print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
  print(x);
  putchar(t);
}
const int md = 1e9 + 7;
inline int add(int x, int y) {
  if (x + y >= md) return x + y - md;
  return x + y;
}
inline void addx(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline int sub(int x, int y) {
  if (x < y) return x - y + md;
  return x - y;
}
inline void subx(int &x, int y) {
  x -= y;
  if (x < 0) x += md;
}
inline int mul(int x, int y) { return 1ull * x * y % md; }
inline int fpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x);
    y >>= 1;
    x = mul(x, x);
  }
  return ans;
}
const int N = 1e5 + 5;
int a[N], f[N], fac[N], inv[N], t[N], tt[N], pw[N];
int n, k, ans;
inline int C(int n, int m) {
  if (n < m || m < 0) return 0;
  return mul(fac[n], mul(inv[m], inv[n - m]));
}
int main() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = mul(fac[i - 1], i);
  inv[N - 1] = fpow(fac[N - 1], md - 2);
  for (int i = N - 1; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
  read(n);
  read(k);
  pw[0] = 1;
  for (int i = 1; i <= n; i++) pw[i] = mul(pw[i - 1], k - 1);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 0; i < n; i++) {
    int tem = fpow(n - i, md - 2);
    int c2 = mul(sub(0, mul(i, k - 1)), tem);
    int c1 = mul(sub(mul(n, k), add(i, mul(n - i, k - 1))), tem);
    int c0 = mul(sub(0, mul(k, i)), tem);
    f[i + 1] = add(c0, mul(c1, f[i]));
    if (i != 0) f[i + 1] = add(f[i + 1], mul(c2, f[i - 1]));
  }
  sort(a + 1, a + n + 1);
  int cnt = 0;
  t[0] = k;
  for (int l = 1, r; l <= n; l = r + 1) {
    r = l;
    while (r < n && a[r + 1] == a[l]) ++r;
    if (a[l] == -1) {
      cnt = r - l + 1;
      continue;
    }
    ++t[r - l + 1];
    --t[0];
  }
  for (int i = 0; i <= n; i++) {
    if (t[i]) {
      for (int j = 0; j <= cnt; j++) {
        tt[i + j] = add(tt[i + j], mul(t[i], mul(C(cnt, j), pw[cnt - j])));
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    ans = add(ans, mul(tt[i], f[i]));
  }
  ans = mul(ans, fpow(fpow(k, cnt), md - 2));
  print(sub(ans, f[n]), '\n');
  return 0;
}

```