#include using namespace std; using ll = long long; template struct mod_int { static const int mod = MOD; unsigned x; mod_int() : x(0) { } mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; } mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; } mod_int &operator/=(mod_int that) { return *this *= that.inverse(); } mod_int operator+(mod_int that) const { return mod_int(*this) += that; } mod_int operator-(mod_int that) const { return mod_int(*this) -= that; } mod_int operator*(mod_int that) const { return mod_int(*this) *= that; } mod_int operator/(mod_int that) const { return mod_int(*this) /= that; } mod_int inverse() const { long long a = x, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return mod_int(u); } }; template istream& operator >> (istream& is, mod_int& val) { long long x; is >> x; val = x; return is; } template ostream& operator << (ostream& os, const mod_int& val) { os << val.get(); return os; } const int mod = 1e9 + 7; using mint = mod_int; const int MAX = 2e6; bool inited = false; mint fac[MAX + 1]; mint rfac[MAX + 1]; void init() { inited = true; fac[0] = 1; for (int i = 1; i <= MAX; i++) { fac[i] = fac[i - 1] * i; } rfac[MAX] = fac[MAX].inverse(); for (int i = MAX; i >= 1; i--) { rfac[i - 1] = rfac[i] * i; } } mint nPr(int n, int r) { if (!inited) init(); return r < 0 || n < r ? 0 : fac[n] * rfac[n - r]; } mint nCr(int n, int r) { if (!inited) init(); return r < 0 || n < r ? 0 : fac[n] * rfac[n - r] * rfac[r]; } mint nHr(int n, int r) { if (!inited) init(); return r == 0 ? 1 : nCr(n + r - 1, r); } ll mod_inv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b > 0) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return (u % m + m) % m; } ll garner(std::vector m, std::vector u, int md) { const int n = m.size(); std::vector inv_prod(n); for (int i = 1; i < n; ++i) { ll prod = m[0] % m[i]; for (int j = 1; j < i; ++j) { prod = (prod * m[j]) % m[i]; } inv_prod[i] = mod_inv(prod, m[i]); } std::vector v(n); v[0] = u[0]; for (int i = 1; i < n; ++i) { ll tmp = v[i - 1]; for (int j = i - 2; j >= 0; --j) { tmp = (tmp * m[j] + v[j]) % m[i]; } v[i] = ((u[i] - tmp) * inv_prod[i]) % m[i]; if (v[i] < 0) v[i] += m[i]; } ll res = v[n - 1]; for (int i = n - 2; i >= 0; --i) { res = (res * m[i] + v[i]) % md; } return res; } ll mod_pow(ll x, ll n, int md) { ll res = 1; while (n) { if (n & 1) (res *= x) %= md; (x *= x) %= md; n >>= 1; } return res; } template class NTT { public: // assertion: v.size() == 2 ^ m static std::vector fft(std::vector v, bool inv) { const int n = v.size(); int ww = mod_pow(PrimitiveRoot, (Mod - 1) / n, Mod); if (inv) ww = mod_inv(ww, Mod); for (int m = n; m >= 2; m >>= 1) { const int mh = m >> 1; int w = 1; for (int i = 0; i < mh; ++i) { for (int j = i; j < n; j += m) { const int k = j + mh; int x = v[j] - v[k]; if (x < 0) x += Mod; v[j] += -Mod + v[k]; if (v[j] < 0) v[j] += Mod; v[k] = (1LL * w * x) % Mod; } w = (1LL * w * ww) % Mod; } ww = (1LL * ww * ww) % Mod; } int i = 0; for (int j = 1; j < n - 1; ++j) { for (int k = n >> 1; k >(i ^= k); k >>= 1); if (j < i) swap(v[i], v[j]); } if (inv) { const int inv_n = mod_inv(n, Mod); for (auto& x : v) { x = (1LL * x * inv_n) % Mod; } } return v; } static std::vector convolution(std::vector f, std::vector g) { int sz = 1; const int m = f.size() + g.size() - 1; while (sz < m) sz *= 2; f.resize(sz), g.resize(sz); f = NTT::fft(std::move(f), false); g = NTT::fft(std::move(g), false); for (int i = 0; i < sz; ++i) { f[i] = (1LL * f[i] * g[i]) % Mod; } return NTT::fft(std::move(f), true); } static int get_mod() { return Mod; } }; using NTT_1 = NTT<167772161, 3>; // 5 * 2^25 + 1 using NTT_2 = NTT<469762049, 3>; // 7 * 2^26 + 1 using NTT_3 = NTT<1224736769, 3>; // 73 * 2^24 + 1 std::vector mod_convolution(std::vector f, std::vector g, const int md) { for (auto& x : f) x %= md; for (auto& y : g) y %= md; const auto v1 = NTT_1::convolution(f, g); const auto v2 = NTT_2::convolution(f, g); const auto v3 = NTT_3::convolution(f, g); vector res(v1.size()); vector m = { NTT_1::get_mod(), NTT_2::get_mod(), NTT_3::get_mod() }; for (int i = 0; i < (int)v1.size(); ++i) { vector u = { v1[i], v2[i], v3[i] }; res[i] = garner(m, u, md); } return res; } vector calc(int lb, int ub, const vector>& a) { if (ub - lb == 1) return a[lb]; int m = (lb + ub) / 2; auto v1 = calc(lb, m, a); auto v2 = calc(m, ub, a); auto v = mod_convolution(v1, v2, mod); while (!v.empty() && v.back() == 0) v.pop_back(); return v; } int main() { init(); int N; mint B; cin >> N >> B; map cnt; for (int i = 0; i < N; i++) { int S; cin >> S; cnt[S]++; } int size = N; vector> aa; for (auto p : cnt) { mint all = nCr(size, p.second) * fac[p.second]; mint x0 = nCr(size - 1, p.second) * fac[p.second]; vector vec; vec.push_back(x0.get()); vec.push_back(((all - x0) * B).get()); aa.emplace_back(vec); size -= p.second; } auto v = calc(0, aa.size(), aa); mint res = 0; for (int i = 0; i < (int)v.size(); i++) { res += mint(v[i]) * i; } cout << res << endl; return 0; }