#include #include #define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++) #define rep(i, n) rep2(i, 0, n) #define all(x) begin(x), end(x) #ifdef ENV_LOCAL #define dump \ if (1) cerr #else #define dump \ if (0) cerr #endif using namespace std; using namespace std::string_literals; using i32 = int32_t; using i64 = int64_t; using f64 = double; using f80 = long double; using vi32 = vector; using vi64 = vector; /* * harudake::modint * * Copyright (c) 2021 prime number * * This software is released under the MIT license. * see https://opensource.org/licenses/MIT * */ namespace harudake { template class static_modint; using modint_1000000007 = static_modint; using modint_998244353 = static_modint; template static_modint add(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val + rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint::make_raw(tmp); } template static_modint sub(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val + MOD - rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint::make_raw(tmp); } template static_modint mul(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val * rhs.val; tmp %= MOD; return static_modint::make_raw(tmp); } // data types must be signed integer inline int64_t inv(const int64_t a, const int64_t p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); }; template static_modint div(const static_modint lhs, const static_modint rhs) { base_t tmp = lhs.val * inv(rhs.val, MOD); tmp %= MOD; return static_modint::make_raw(tmp); } template static_modint pow(const static_modint base, const uint64_t index) { if (index == 0) return static_modint{1}; if (index % 2 == 1) { return pow(base, index - 1) * base; } else { auto half = pow(base, index / 2); return half * half; } } template class static_modint { using modint = static_modint; public: static constexpr base_t mod = MOD; static_modint() : val(0) {} static_modint(const base_t x) : val(x % MOD) {} static_modint(const modint&) = default; modint& operator=(const modint&) = default; modint& operator=(const base_t x) { val = x % MOD; return *this; } modint operator-() const { return val == 0 ? 0 : MOD - val; } explicit operator base_t() const { return val; } base_t get() const { return val; } constexpr base_t get_mod() const { return mod; } static modint make_raw(const base_t raw) { modint res; res.val = raw; return res; } private: friend modint add(const modint, const modint); friend modint sub(const modint, const modint); friend modint mul(const modint, const modint); friend modint div(const modint, const modint); base_t val; }; template static_modint operator+(const static_modint lhs, const static_modint rhs) { return add(lhs, rhs); } template static_modint operator-(const static_modint lhs, const static_modint rhs) { return sub(lhs, rhs); } template static_modint operator*(const static_modint lhs, const static_modint rhs) { return mul(lhs, rhs); } template static_modint operator/(const static_modint lhs, const static_modint rhs) { return div(lhs, rhs); } template static_modint operator^(const static_modint lhs, const uint64_t rhs) { return pow(lhs, rhs); } template static_modint& operator+=(static_modint& lhs, const static_modint rhs) { return lhs = lhs + rhs; } template static_modint& operator-=(static_modint& lhs, const static_modint rhs) { return lhs = lhs - rhs; } template static_modint& operator*=(static_modint& lhs, const static_modint rhs) { return lhs = lhs * rhs; } template static_modint& operator/=(static_modint& lhs, const static_modint rhs) { return lhs = lhs / rhs; } template static_modint& operator^=(static_modint& lhs, const uint64_t rhs) { return lhs = lhs ^ rhs; } } // namespace harudake using namespace harudake; using modint = modint_998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i64 MAX_F = 200001; vector fact(MAX_F); fact[0] = modint(1); rep(i, MAX_F - 1) fact[i + 1] = fact[i] * modint(i + 1); vector invf(MAX_F); invf.back() = modint(1) / fact.back(); rep(ri, MAX_F - 1) { i64 i = MAX_F - ri - 1; invf[i - 1] = invf[i] * modint(i); } auto comb = [&](i64 n, i64 k) { return fact[n] * invf[k] * invf[n - k]; }; i64 t; cin >> t; rep(tnum, t) { i64 n, m; cin >> n >> m; vi64 a(n); rep(i, n) cin >> a[i]; sort(all(a)); map hist; rep(i, n) { ++hist[a[i]]; } vector> vp; for (auto&& [x, y] : hist) { vp.emplace_back(x, y); } reverse(all(vp)); map, modint> dp; dp[make_pair(0, 0)] = modint(1); i64 total = 0; for (auto&& [x, y] : vp) { map, modint> nxt; for (auto&& [key, cnt] : dp) { auto [left, num] = key; i64 right = total - left; rep(p, y + 1) { i64 q = y - p; i64 llr = max(left, n - left - p); i64 rlr = max(right, n - right - q); if (p > 0 && llr != x) continue; if (q > 0 && rlr != x) continue; i64 new_num = num + 1; if (p > 0 && q > 0) ++new_num; nxt[make_pair(left + p, new_num)] += cnt * comb(y, p); } } swap(dp, nxt); total += y; } modint ans = 0; for (auto&& [key, cnt] : dp) { auto [left, num] = key; if (m < num) continue; ans += cnt * comb(m, num); } ans /= modint(2); cout << ans.get() << endl; } return 0; }