#include using i64 = long long; template constexpr T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; } template struct MInt { int x; constexpr MInt() : x{} {} constexpr MInt(i64 x) : x{norm(x % getMod())} {} static int Mod; constexpr static int getMod() { if (P > 0) { return P; } else { return Mod; } } constexpr static void setMod(int Mod_) { Mod = Mod_; } constexpr int norm(int x) const { if (x < 0) { x += getMod(); } if (x >= getMod()) { x -= getMod(); } return x; } constexpr int val() const { return x; } explicit constexpr operator int() const { return x; } constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; } constexpr MInt inv() const { assert(x != 0); return power(*this, getMod() - 2); } constexpr MInt &operator*=(MInt rhs) & { x = 1LL * x * rhs.x % getMod(); return *this; } constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; } constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; } constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); } friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; } friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; } friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; } friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; } friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; } friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); } friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); } friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); } }; template<> int MInt<0>::Mod = 1; template constexpr MInt

CInv = MInt

(V).inv(); constexpr int P = 998244353; using Z = MInt

; std::vector rev; template std::vector> roots{0, 1}; template constexpr MInt

findPrimitiveRoot() { MInt

i = 2; int k = __builtin_ctz(P - 1); while (true) { if (power(i, 1 << (k - 1)) != 1 && power(i, 1 << k) == 1) { break; } i += 1; } return i; } template constexpr MInt

primitiveRoot = findPrimitiveRoot

(); template<> constexpr MInt<998244353> primitiveRoot<998244353> {31}; template constexpr void dft(std::vector> &a) { int n = a.size(); if (int(rev.size()) != n) { int k = __builtin_ctz(n) - 1; rev.resize(n); for (int i = 0; i < n; i++) { rev[i] = rev[i >> 1] >> 1 | (i & 1) << k; } } for (int i = 0; i < n; i++) { if (rev[i] < i) { std::swap(a[i], a[rev[i]]); } } if (roots

.size() < n) { int k = __builtin_ctz(roots

.size()); roots

.resize(n); while ((1 << k) < n) { auto e = power(primitiveRoot

, 1 << (__builtin_ctz(P - 1) - k - 1)); for (int i = 1 << (k - 1); i < (1 << k); i++) { roots

[2 * i] = roots

[i]; roots

[2 * i + 1] = roots

[i] * e; } k++; } } for (int k = 1; k < n; k *= 2) { for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { MInt

u = a[i + j]; MInt

v = a[i + j + k] * roots

[k + j]; a[i + j] = u + v; a[i + j + k] = u - v; } } } } template constexpr void idft(std::vector> &a) { int n = a.size(); std::reverse(a.begin() + 1, a.end()); dft(a); MInt

inv = (1 - P) / n; for (int i = 0; i < n; i++) { a[i] *= inv; } } template struct Poly { using Value = MInt

; std::vector a; constexpr Poly() : a{} {} explicit constexpr Poly(int n) : a(n) {} template explicit constexpr Poly(int n, F f) : a(n) { for (int i = 0; i < n; i++) { a[i] = f(i); } } explicit constexpr Poly(const std::vector &a) : a(a) {} explicit constexpr Poly(const std::initializer_list &a) : a(a) {} template> explicit constexpr Poly(InputIt first, InputIt last) : a(first, last) {} constexpr int size() const { return a.size(); } explicit constexpr operator std::vector() const { return a; } constexpr Value operator[](int idx) const { if (idx < size()) { return a[idx]; } else { return 0; } } constexpr Value &operator[](int idx) { return a[idx]; } constexpr Poly shift(int k) const { if (k >= 0) { auto b = a; b.insert(b.begin(), k, 0); return Poly(b); } else if (size() <= -k) { return Poly(); } else { return Poly(a.begin() + (-k), a.end()); } } constexpr Poly resize(int k) const { Poly f{a}; f.a.resize(k); return f; } constexpr friend Poly operator+(const Poly &a, const Poly &b) { std::vector res(std::max(a.size(), b.size())); for (int i = 0; i < int(res.size()); i++) { res[i] = a[i] + b[i]; } return Poly(res); } constexpr friend Poly operator-(const Poly &a, const Poly &b) { std::vector res(std::max(a.size(), b.size())); for (int i = 0; i < int(res.size()); i++) { res[i] = a[i] - b[i]; } return Poly(res); } constexpr friend Poly operator-(const Poly &a) { std::vector res(a.size()); for (int i = 0; i < int(res.size()); i++) { res[i] = -a[i]; } return Poly(res); } constexpr friend Poly operator*(Poly a, Poly b) { if (a.size() == 0 || b.size() == 0) { return Poly(); } if (a.size() < b.size()) { std::swap(a, b); } if (b.size() < 128) { Poly c(a.size() + b.size() - 1); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b.size(); j++) { c[i + j] += a[i] * b[j]; } } return c; } int sz = 1, tot = a.size() + b.size() - 1; while (sz < tot) { sz *= 2; } a.a.resize(sz); b.a.resize(sz); dft(a.a); dft(b.a); for (int i = 0; i < sz; ++i) { a.a[i] = a[i] * b[i]; } idft(a.a); a.resize(tot); return a; } constexpr friend Poly operator*(Value a, Poly b) { for (int i = 0; i < int(b.size()); i++) { b[i] *= a; } return b; } constexpr friend Poly operator*(Poly a, Value b) { for (int i = 0; i < int(a.size()); i++) { a[i] *= b; } return a; } constexpr Poly &operator+=(Poly b) { return (*this) = (*this) + b; } constexpr Poly &operator-=(Poly b) { return (*this) = (*this) - b; } constexpr Poly &operator*=(Poly b) { return (*this) = (*this) * b; } constexpr Poly &operator*=(Value b) { return (*this) = (*this) * b; } constexpr Poly deriv() const { if (a.empty()) { return Poly(); } std::vector res(size() - 1); for (int i = 0; i < size() - 1; ++i) { res[i] = (i + 1) * a[i + 1]; } return Poly(res); } constexpr Poly integr() const { std::vector res(size() + 1); for (int i = 0; i < size(); ++i) { res[i + 1] = a[i] / (i + 1); } return Poly(res); } constexpr Poly inv(int m) const { Poly x{a[0].inv()}; int k = 1; while (k < m) { k *= 2; x = (x * (Poly{2} - resize(k) * x)).resize(k); } return x.resize(m); } constexpr Poly log(int m) const { return (deriv() * inv(m)).integr().resize(m); } constexpr Poly exp(int m) const { Poly x{1}; int k = 1; while (k < m) { k *= 2; x = (x * (Poly{1} - x.log(k) + resize(k))).resize(k); } return x.resize(m); } constexpr Poly pow(int k, int m) const { int i = 0; while (i < size() && a[i] == 0) { i++; } if (i == size() || 1LL * i * k >= m) { return Poly(m); } Value v = a[i]; auto f = shift(-i) * v.inv(); return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k); } constexpr Poly sqrt(int m) const { Poly x{1}; int k = 1; while (k < m) { k *= 2; x = (x + (resize(k) * x.inv(k)).resize(k)) * CInv<2, P>; } return x.resize(m); } constexpr Poly mulT(Poly b) const { if (b.size() == 0) { return Poly(); } int n = b.size(); std::reverse(b.a.begin(), b.a.end()); return ((*this) * b).shift(-(n - 1)); } constexpr std::vector eval(std::vector x) const { if (size() == 0) { return std::vector(x.size(), 0); } const int n = std::max(int(x.size()), size()); std::vector q(4 * n); std::vector ans(x.size()); x.resize(n); std::function build = [&](int p, int l, int r) { if (r - l == 1) { q[p] = Poly{1, -x[l]}; } else { int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); q[p] = q[2 * p] * q[2 * p + 1]; } }; build(1, 0, n); std::function work = [&](int p, int l, int r, const Poly &num) { if (r - l == 1) { if (l < int(ans.size())) { ans[l] = num[0]; } } else { int m = (l + r) / 2; work(2 * p, l, m, num.mulT(q[2 * p + 1]).resize(m - l)); work(2 * p + 1, m, r, num.mulT(q[2 * p]).resize(r - m)); } }; work(1, 0, n, mulT(q[1].inv(n))); return ans; } constexpr auto begin() const { return a.begin(); } constexpr auto end() const { return a.end(); } }; struct Comb { int n; std::vector _fac; std::vector _invfac; std::vector _inv; Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {} Comb(int n) : Comb() { init(n); } void init(int m) { if (m <= n) return; _fac.resize(m + 1); _invfac.resize(m + 1); _inv.resize(m + 1); for (int i = n + 1; i <= m; i++) { _fac[i] = _fac[i - 1] * i; } _invfac[m] = _fac[m].inv(); for (int i = m; i > n; i--) { _invfac[i - 1] = _invfac[i] * i; _inv[i] = _invfac[i] * _fac[i - 1]; } n = m; } Z fac(int m) { if (m > n) init(2 * m); return _fac[m]; } Z invfac(int m) { if (m > n) init(2 * m); return _invfac[m]; } Z inv(int m) { if (m > n) init(2 * m); return _inv[m]; } Z binom(int n, int m) { if (n < m || m < 0) return 0; return fac(n) * invfac(m) * invfac(n - m); } } comb; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int M, N; std::cin >> M >> N; std::vector A(N); for (int i = 0; i < N; i++) { std::cin >> A[i]; A[i] -= 1; } std::vector c(M); for (int i = 0; i < N; i++) { c[A[i]] += 1; } std::function(int, int)> prod = [&](int l, int r) { if (r - l == 1) { return Poly{-c[l], 1}; } int m = (l + r) / 2; return prod(l, m) * prod(m, r); }; auto pr = prod(0, M); std::vector x(N + 1); std::iota(x.begin(), x.end(), 0); auto val = pr.eval(x); std::vector f(N + 1); int maxc = *std::max_element(c.begin(), c.end()); for (int i = maxc; i <= N; i++) { if (i == maxc) { f[i] = 1; for (int j = 0; j < M; j++) { f[i] *= comb.invfac(i - c[j]); } } else { f[i] = f[i - 1] / val[i]; } } for (int i = maxc; i <= N; i++) { f[i] *= power(comb.fac(i), M); } for (int i = 0; i <= N; i++) { f[i] *= comb.invfac(i); if (i % 2 == 1) { f[i] *= -1; } } f = std::vector((Poly(f) * Poly(N + 1, [&](int n) { return comb.invfac(n); })).resize(N + 1)); for (int i = 0; i <= N; i++) { f[i] *= comb.fac(i); if (i % 2 == 1) { f[i] *= -1; } } auto ans = std::accumulate(f.begin(), f.end(), Z(0)); std::cout << ans << "\n"; return 0; }