#include #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) #define popcount(x) __builtin_popcountll(x) #define pb push_back #define eb emplace_back #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0) #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using ll = long long; using ld = long double; using P = pair; using LP = pair; using vi = vector; using vvi = vector; using vl = vector; using vvl = vector; using vd = vector; using vvd = vector; using vs = vector; using vc = vector; using vvc = vector; using vb = vector; using vvb = vector; using vp = vector

; using vvp = vector; template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second; } template ostream &operator<<(ostream &os, const pair &p) { return os << '{' << p.first << ", " << p.second << '}'; } template istream &operator>>(istream &is, tuple &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template ostream &operator<<(ostream &os, const tuple &t) { return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}'; } template istream &operator>>(istream &is, vector &v) { for (T &t:v) { is >> t; } return is; } template ostream &operator<<(ostream &os, const vector &v) { os << '['; rep(i, v.size())os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template void vecout(const vector &v, char div = '\n') { rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div); } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void scan() {} template void scan(Head &head, Tail &... tail) { cin >> head; scan(tail...); } template void print(const T &t) { cout << t << '\n'; } template void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template void fin(const T &... a) { print(a...); exit(0); } struct Init_io { Init_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << boolalpha << fixed << setprecision(15); cerr << boolalpha << fixed << setprecision(15); } } init_io; const string yes[] = {"no", "yes"}; const string Yes[] = {"No", "Yes"}; const string YES[] = {"NO", "YES"}; const int inf = 1001001001; const ll linf = 1001001001001001001; template vector cumsum(const vector &v, bool shift_one = true) { int n = v.size(); vector res; if (shift_one) { res.resize(n + 1); rep(i, n) res[i + 1] = res[i] + v[i]; } else { res.resize(n); if (n) { res[0] = v[0]; rep(i, 1, n) res[i] = res[i - 1] + v[i]; } } return res; } vvi graph(int n, int m, bool directed = false, int origin = 1) { vvi G(n); rep(_, m) { INT(u, v); u -= origin, v -= origin; G[u].pb(v); if (!directed) G[v].pb(u); } return G; } template vector>> weighted_graph(int n, int m, bool directed = false, int origin = 1) { vector>> G(n); rep(_, m) { int u, v; T w; scan(u, v, w); u -= origin, v -= origin; G[u].eb(v, w); if (!directed) G[v].eb(u, w); } return G; } template void resemble(vector &v) {} template void resemble(vector &v, vector &head, Tail &...tail) { for (T &e : head) v.pb(e); resemble(v, tail...); } template void renumber(vector &v) {} template void renumber(vector &v, vector &head, Tail &...tail) { for (T &e : head) e = lower_bound(all(v), e) - v.begin(); renumber(v, tail...); } template vector zip(vector &head, Tail &... tail) { vector v; resemble(v, head, tail...); sort(all(v)); v.erase(unique(all(v)), v.end()); renumber(v, head, tail...); return v; } template class modint { ll x; public: constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {} static constexpr int get_mod() { return mod; } constexpr int val() const { return x; } constexpr modint operator-() const { return modint(-x); } constexpr modint &operator+=(const modint &a) { if ((x += a.val()) >= mod) x -= mod; return *this; } constexpr modint &operator++() { return *this += 1; } constexpr modint &operator-=(const modint &a) { if ((x += mod - a.val()) >= mod) x -= mod; return *this; } constexpr modint &operator--() { return *this -= 1; } constexpr modint &operator*=(const modint &a) { (x *= a.val()) %= mod; return *this; } constexpr modint operator+(const modint &a) const { modint res(*this); return res += a; } constexpr modint operator-(const modint &a) const { modint res(*this); return res -= a; } constexpr modint operator*(const modint &a) const { modint res(*this); return res *= a; } constexpr modint pow(ll t) const { modint res = 1, a(*this); while (t > 0) { if (t & 1) res *= a; t >>= 1; a *= a; } return res; } template friend istream &operator>>(istream &, modint &); // for prime mod constexpr modint inv() const { return pow(mod - 2); } constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); } constexpr modint operator/(const modint &a) const { modint res(*this); return res /= a; } }; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; template istream &operator>>(istream &is, modint &a) { return is >> a.x; } template constexpr ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } template constexpr bool operator==(const modint &a, const modint &b) { return a.val() == b.val(); } template constexpr bool operator!=(const modint &a, const modint &b) { return a.val() != b.val(); } template constexpr modint &operator++(modint &a) { return a += 1; } template constexpr modint &operator--(modint &a) { return a -= 1; } using mint = modint998244353; using vm = vector; using vvm = vector; class NTT { int pr; constexpr ll pow_mod(ll x, ll n, int m) { if (m == 1) return 0; ll res = 1; ll now = x % m; while (n > 0) { if (n & 1) res = (res * now) % m; now = (now * now) % m; n >>= 1; } return res; } constexpr int primitive_root(int mod) { if (mod == 2) return 1; if (mod == 167772161) return 3; if (mod == 469762049) return 3; if (mod == 754974721) return 11; if (mod == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (mod - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; (ll) i * i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) { x /= i; } } } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (pow_mod(g, (mod - 1) / divs[i], mod) == 1) { ok = false; break; } } if (ok) return g; } } public: bool first = true; mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i] mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i] void init(int mod) { first = false; pr = primitive_root(mod); mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1 int cnt2 = __builtin_ctz(mint::get_mod() - 1); mint e = mint(pr).pow((mint::get_mod() - 1) >> cnt2), ie = e.inv(); for (int i = cnt2; i >= 2; i--) { // e^(2^i) == 1 es[i - 2] = e; ies[i - 2] = ie; e *= e; ie *= ie; } mint now = 1; for (int i = 0; i <= cnt2 - 2; i++) { sum_e[i] = es[i] * now; now *= ies[i]; } now = 1; for (int i = 0; i <= cnt2 - 2; i++) { sum_ie[i] = ies[i] * now; now *= es[i]; } } void operator()(vector &a, bool inverse = false) { int n = a.size(); int h = __builtin_ctz(n); if (inverse) { rrep(ph, h + 1, 1) { int w = 1 << (ph - 1), p = 1 << (h - ph); mint now = 1; rep(s, w) { int offset = s << (h - ph + 1); rep(i, p) { auto l = a[i + offset]; auto r = a[i + offset + p]; a[i + offset] = l + r; a[i + offset + p] = (l - r) * now; } now *= sum_ie[__builtin_ctz(~(unsigned int) (s))]; } } } else { rep(ph, 1, h + 1) { int w = 1 << (ph - 1), p = 1 << (h - ph); mint now = 1; rep(s, w) { int offset = s << (h - ph + 1); rep(i, p) { auto l = a[i + offset]; auto r = a[i + offset + p] * now; a[i + offset] = l + r; a[i + offset + p] = l - r; } now *= sum_e[__builtin_ctz(~(unsigned int) (s))]; } } } } } ntt; vm convolution(const vm &a, const vm &b) { if (a.empty()) return {}; if (b.empty()) return {}; int s = a.size() + b.size() - 1; if (min(a.size(), b.size()) <= 50) { vm res(s); if (a.size() >= b.size()) { rep(i, a.size()) rep(j, b.size()) res[i + j] += a[i] * b[j]; } else { rep(j, b.size()) rep(i, a.size()) res[i + j] += a[i] * b[j]; } return res; } int t = 1; while (t < s) t *= 2; vm A(t), B(t); rep(i, a.size()) A[i] = a[i]; rep(i, b.size()) B[i] = b[i]; if (ntt.first) ntt.init(mint::get_mod()); ntt(A); ntt(B); rep(i, t) A[i] *= B[i]; ntt(A, true); vm res(s); mint it = mint(t).inv(); rep(i, s) res[i] = A[i] * it; return res; } template class polynomial : public vector { public: using vector::vector; constexpr T eval(T x) const { T res = 0; T now = 1; rep(i, this->size()) { res += (*this)[i] * now; now *= x; } return res; } // return f'(x) constexpr polynomial differ() const { vector res; rep2(i, 1, this->size()) res.pb((*this)[i] * i); return polynomial(all(res)); } // return ∫ f(x)dx constexpr polynomial integral() const { int n = this->size(); if (n == 0) return vector(); vector res = {0}; rep(i, n) res.pb((*this)[i] / (i + 1)); return polynomial(all(res)); }; constexpr polynomial operator+(const polynomial &a) const { vector res(max(this->size(), a.size())); rep(i, this->size()) res[i] += (*this)[i]; rep(i, a.size()) res[i] += a[i]; return polynomial(all(res)); } constexpr polynomial operator-(const polynomial &a) const { vector res(max(this->size(), a.size())); rep(i, this->size()) res[i] += (*this)[i]; rep(i, a.size()) res[i] -= a[i]; return polynomial(all(res)); } constexpr polynomial operator*(const polynomial &a) const { vector res = convolution(*this, a); return polynomial(all(res)); } constexpr polynomial operator*(T k) const { polynomial res(*this); rep(i, res.size()) res[i] *= k; return res; } constexpr polynomial &operator+=(const polynomial &a) { return *this = *this + a; } constexpr polynomial &operator-=(const polynomial &a) { return *this = *this - a; } constexpr polynomial &operator*=(const polynomial &a) { return *this = *this * a; } // P *= (ax + b) constexpr void multiply(T a = 0, T b = 1) { int n = this->size(); this->push_back(T(0)); rrep(i, n) { (*this)[i + 1] += (*this)[i] * a; (*this)[i] *= b; } } // P /= (ax + b) constexpr void divide(T a = 0, T b = 1) { int n = this->size(); assert(n >= 2); assert(a != 0 or b != 0); if (b == T(0)) { assert((*this)[0] == T(0)); T inv = T(1) / a; rep(i, n - 1) (*this)[i] = (*this)[i + 1] * inv; this->back() = T(0); } else { T inv = T(1) / b; rep(i, n - 1) { (*this)[i] *= inv; (*this)[i + 1] -= (*this)[i] * a; } assert(this->back() == T(0)); } } }; using poly = polynomial; int main() { INT(n, k); vi a(n); cin >> a; int sz = zip(a).size(); vi cnt(sz); rep(i, n) cnt[a[i]]++; vvp rq(n + 1); int sum = 0; vector ps(sz, poly(k + 1)); rep(i, sz) { rq[cnt[i]].eb(i, sum); // rep(j, sum + 1) rep(l, k + 1) ps[i][l] += dp[cnt[i]][j][l]; sum += cnt[i]; } rep(i, n + 1) reverse(all(rq[i])); vvm dp(n + 1, vm(k + 2)); vvm ndp(n + 1, vm(k + 2)); dp[0][0] = 1; dp[1][1] = -1; rep(i, n + 1) { rep(j, n) rep(s, k + 1) { for (auto[pos, lim] : rq[i]) { if (j > lim) break; ps[pos][s] += dp[j][s]; } ndp[j][s + j] += dp[j][s]; dp[j + 1][s + 1] += dp[j][s]; dp[j][s] = 0; } swap(dp, ndp); } poly ans(k + 1); ans[0] = 1; rep(i, sz) { ans *= ps[i]; ans.resize(k + 1); } print(ans[k]); }