#define PROBLEM "https://yukicoder.me/problems/no/2005" #include #include #include using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } #include #include #include #include #include #include #include #include namespace suisen { // ! utility template using constraints_t = std::enable_if_t, std::nullptr_t>; template constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) { if constexpr (cond_v) { return std::forward(then); } else { return std::forward(or_else); } } // ! function template using is_same_as_invoke_result = std::is_same, ReturnType>; template using is_uni_op = is_same_as_invoke_result; template using is_bin_op = is_same_as_invoke_result; template using is_comparator = std::is_same, bool>; // ! integral template >> constexpr int bit_num = std::numeric_limits>::digits; template struct is_nbit { static constexpr bool value = bit_num == n; }; template static constexpr bool is_nbit_v = is_nbit::value; // ? template struct safely_multipliable {}; template <> struct safely_multipliable { using type = long long; }; template <> struct safely_multipliable { using type = __int128_t; }; template <> struct safely_multipliable { using type = unsigned long long; }; template <> struct safely_multipliable { using type = __uint128_t; }; template <> struct safely_multipliable { using type = __uint128_t; }; template <> struct safely_multipliable { using type = float; }; template <> struct safely_multipliable { using type = double; }; template <> struct safely_multipliable { using type = long double; }; template using safely_multipliable_t = typename safely_multipliable::type; template struct rec_value_type { using type = T; }; template struct rec_value_type> { using type = typename rec_value_type::type; }; template using rec_value_type_t = typename rec_value_type::type; } // namespace suisen #include /** * refernce: https://37zigen.com/tonelli-shanks-algorithm/ * calculates x s.t. x^2 = a mod p in O((log p)^2). */ template std::optional safe_sqrt(mint a) { static int p = mint::mod(); if (a == 0) return std::make_optional(0); if (p == 2) return std::make_optional(a); if (a.pow((p - 1) / 2) != 1) return std::nullopt; mint b = 1; while (b.pow((p - 1) / 2) == 1) ++b; static int tlz = __builtin_ctz(p - 1), q = (p - 1) >> tlz; mint x = a.pow((q + 1) / 2); b = b.pow(q); for (int shift = 2; x * x != a; ++shift) { mint e = a.inv() * x * x; if (e.pow(1 << (tlz - shift)) != 1) x *= b; b *= b; } return std::make_optional(x); } /** * calculates x s.t. x^2 = a mod p in O((log p)^2). * if not exists, raises runtime error. */ template auto sqrt(mint a) -> decltype(mint::mod(), mint()) { return *safe_sqrt(a); } template auto log(mint a) -> decltype(mint::mod(), mint()) { assert(a == 1); return 0; } template auto exp(mint a) -> decltype(mint::mod(), mint()) { assert(a == 0); return 1; } template auto pow(mint a, T b) -> decltype(mint::mod(), mint()) { return a.pow(b); } template auto inv(mint a) -> decltype(mint::mod(), mint()) { return a.inv(); } namespace suisen { template class inv_mods { public: inv_mods() {} inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = {0, 1}, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector invs; static constexpr int mod = mint::mod(); }; template std::vector inv_mods::invs{}; } namespace suisen { template struct FPSNaive : std::vector { static inline int MAX_DEG = std::numeric_limits::max() / 2; using value_type = T; using element_type = rec_value_type_t; using std::vector::vector; FPSNaive(const std::initializer_list l) : std::vector::vector(l) {} FPSNaive(const std::vector& v) : std::vector::vector(v) {} static void set_max_deg(int max_deg) { FPSNaive::MAX_DEG = max_deg; } const value_type operator[](int n) const { return n <= deg() ? unsafe_get(n) : value_type{ 0 }; } value_type& operator[](int n) { return ensure_deg(n), unsafe_get(n); } int size() const { return std::vector::size(); } int deg() const { return size() - 1; } int normalize() { while (size() and this->back() == value_type{ 0 }) this->pop_back(); return deg(); } FPSNaive& cut_inplace(int max_deg) { if (deg() > max_deg) this->resize(std::max(0, max_deg + 1)); return *this; } FPSNaive cut(int max_deg) const { return FPSNaive(*this).cut_inplace(max_deg); } FPSNaive operator+() const { return FPSNaive(*this); } FPSNaive operator-() const { FPSNaive f(*this); for (auto& e : f) e = -e; return f; } FPSNaive& operator++() { return ++(*this)[0], * this; } FPSNaive& operator--() { return --(*this)[0], * this; } FPSNaive& operator+=(const value_type x) { return (*this)[0] += x, *this; } FPSNaive& operator-=(const value_type x) { return (*this)[0] -= x, *this; } FPSNaive& operator+=(const FPSNaive& g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) += g.unsafe_get(i); return *this; } FPSNaive& operator-=(const FPSNaive& g) { ensure_deg(g.deg()); for (int i = 0; i <= g.deg(); ++i) unsafe_get(i) -= g.unsafe_get(i); return *this; } FPSNaive& operator*=(const FPSNaive& g) { return *this = *this * g; } FPSNaive& operator*=(const value_type x) { for (auto& e : *this) e *= x; return *this; } FPSNaive& operator/=(const FPSNaive& g) { return *this = *this / g; } FPSNaive& operator%=(const FPSNaive& g) { return *this = *this % g; } FPSNaive& operator<<=(const int shamt) { this->insert(this->begin(), shamt, value_type{ 0 }); return *this; } FPSNaive& operator>>=(const int shamt) { if (shamt > size()) this->clear(); else this->erase(this->begin(), this->begin() + shamt); return *this; } friend FPSNaive operator+(FPSNaive f, const FPSNaive& g) { f += g; return f; } friend FPSNaive operator+(FPSNaive f, const value_type& x) { f += x; return f; } friend FPSNaive operator-(FPSNaive f, const FPSNaive& g) { f -= g; return f; } friend FPSNaive operator-(FPSNaive f, const value_type& x) { f -= x; return f; } friend FPSNaive operator*(const FPSNaive& f, const FPSNaive& g) { if (f.empty() or g.empty()) return FPSNaive{}; const int n = f.size(), m = g.size(); FPSNaive h(std::min(MAX_DEG + 1, n + m - 1)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (i + j > MAX_DEG) break; h.unsafe_get(i + j) += f.unsafe_get(i) * g.unsafe_get(j); } return h; } friend FPSNaive operator*(FPSNaive f, const value_type& x) { f *= x; return f; } friend FPSNaive operator/(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).first); } friend FPSNaive operator%(FPSNaive f, const FPSNaive& g) { return std::move(f.div_mod(g).second); } friend FPSNaive operator*(const value_type x, FPSNaive f) { f *= x; return f; } friend FPSNaive operator<<(FPSNaive f, const int shamt) { f <<= shamt; return f; } friend FPSNaive operator>>(FPSNaive f, const int shamt) { f >>= shamt; return f; } std::pair div_mod(FPSNaive g) const { FPSNaive f = *this; const int fd = f.normalize(), gd = g.normalize(); assert(gd >= 0); if (fd < gd) return { FPSNaive{}, f }; if (gd == 0) return { f *= g.unsafe_get(0).inv(), FPSNaive{} }; const int k = f.deg() - gd; value_type head_inv = g.unsafe_get(gd).inv(); FPSNaive q(k + 1); for (int i = k; i >= 0; --i) { value_type div = f.unsafe_get(i + gd) * head_inv; q.unsafe_get(i) = div; for (int j = 0; j <= gd; ++j) f.unsafe_get(i + j) -= div * g.unsafe_get(j); } return { q, f.cut_inplace(gd - 1) }; } friend bool operator==(const FPSNaive& f, const FPSNaive& g) { const int n = f.size(), m = g.size(); if (n < m) return g == f; for (int i = 0; i < m; ++i) if (f.unsafe_get(i) != g.unsafe_get(i)) return false; for (int i = m; i < n; ++i) if (f.unsafe_get(i) != 0) return false; return true; } friend bool operator!=(const FPSNaive& f, const FPSNaive& g) { return not (f == g); } FPSNaive mul(const FPSNaive& g, int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); if (this->empty() or g.empty()) return FPSNaive{}; const int n = size(), m = g.size(); FPSNaive h(std::min(max_deg + 1, n + m - 1)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (i + j > max_deg) break; h.unsafe_get(i + j) += unsafe_get(i) * g.unsafe_get(j); } return h; } FPSNaive diff() const { if (this->empty()) return {}; FPSNaive g(size() - 1); for (int i = 1; i <= deg(); ++i) g.unsafe_get(i - 1) = unsafe_get(i) * i; return g; } FPSNaive intg() const { const int n = size(); FPSNaive g(n + 1); for (int i = 0; i < n; ++i) g.unsafe_get(i + 1) = unsafe_get(i) * invs[i + 1]; if (g.deg() > MAX_DEG) g.cut_inplace(MAX_DEG); return g; } FPSNaive inv(int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); FPSNaive g(max_deg + 1); const value_type inv_f0 = ::inv(unsafe_get(0)); g.unsafe_get(0) = inv_f0; for (int i = 1; i <= max_deg; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) -= g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= inv_f0; } return g; } FPSNaive exp(int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); assert(unsafe_get(0) == value_type{ 0 }); FPSNaive g(max_deg + 1); g.unsafe_get(0) = value_type{ 1 }; for (int i = 1; i <= max_deg; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) += j * g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= invs[i]; } return g; } FPSNaive log(int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); assert(unsafe_get(0) == value_type{ 1 }); FPSNaive g(max_deg + 1); g.unsafe_get(0) = value_type{ 0 }; for (int i = 1; i <= max_deg; ++i) { g.unsafe_get(i) = i * (*this)[i]; for (int j = 1; j < i; ++j) g.unsafe_get(i) -= (i - j) * g.unsafe_get(i - j) * (*this)[j]; g.unsafe_get(i) *= invs[i]; } return g; } FPSNaive pow(const long long k, int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); if (k == 0) { FPSNaive res(max_deg + 1); res[0] = 1; return res; } int z = 0; while (z < size() and unsafe_get(z) == value_type{ 0 }) ++z; if (z == size() or z > max_deg / k) return FPSNaive(max_deg + 1, 0); const int d = max_deg - z * k; FPSNaive g(d + 1); const value_type inv_f0 = ::inv(unsafe_get(z)); g.unsafe_get(0) = unsafe_get(z).pow(k); for (int i = 1; i <= d; ++i) { for (int j = 1; j <= i; ++j) g.unsafe_get(i) += (element_type{ k } *j - (i - j)) * g.unsafe_get(i - j) * (*this)[z + j]; g.unsafe_get(i) *= inv_f0 * invs[i]; } g <<= z * k; return g; } std::optional safe_sqrt(int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); int dl = 0; while (dl < size() and unsafe_get(dl) == value_type{ 0 }) ++dl; if (dl == size()) return FPSNaive(max_deg + 1, 0); if (dl & 1) return std::nullopt; const int d = max_deg - dl / 2; FPSNaive g(d + 1); auto opt_g0 = ::safe_sqrt((*this)[dl]); if (not opt_g0.has_value()) return std::nullopt; g.unsafe_get(0) = *opt_g0; value_type inv_2g0 = ::inv(2 * g.unsafe_get(0)); for (int i = 1; i <= d; ++i) { g.unsafe_get(i) = (*this)[dl + i]; for (int j = 1; j < i; ++j) g.unsafe_get(i) -= g.unsafe_get(j) * g.unsafe_get(i - j); g.unsafe_get(i) *= inv_2g0; } g <<= dl / 2; return g; } FPSNaive sqrt(int max_deg = -1) const { if (max_deg < 0) max_deg = deg(); return *safe_sqrt(max_deg); } value_type eval(value_type x) const { value_type y = 0; for (int i = size() - 1; i >= 0; --i) y = y * x + unsafe_get(i); return y; } private: static inline inv_mods invs; void ensure_deg(int d) { if (deg() < d) this->resize(d + 1, value_type{ 0 }); } const value_type& unsafe_get(int i) const { return std::vector::operator[](i); } value_type& unsafe_get(int i) { return std::vector::operator[](i); } }; } // namespace suisen template auto sqrt(suisen::FPSNaive a) -> decltype(mint::mod(), suisen::FPSNaive{}) { return a.sqrt(suisen::FPSNaive::MAX_DEG == std::numeric_limits::max() / 2 ? suisen::FPSNaive::MAX_DEG : a.deg()); } template auto log(suisen::FPSNaive a) -> decltype(mint::mod(), suisen::FPSNaive{}) { return a.log(suisen::FPSNaive::MAX_DEG == std::numeric_limits::max() / 2 ? suisen::FPSNaive::MAX_DEG : a.deg()); } template auto exp(suisen::FPSNaive a) -> decltype(mint::mod(), suisen::FPSNaive{}) { return a.exp(suisen::FPSNaive::MAX_DEG == std::numeric_limits::max() / 2 ? suisen::FPSNaive::MAX_DEG : a.deg()); } template auto pow(suisen::FPSNaive a, T b) -> decltype(mint::mod(), suisen::FPSNaive{}) { return a.pow(b, suisen::FPSNaive::MAX_DEG == std::numeric_limits::max() / 2 ? suisen::FPSNaive::MAX_DEG : a.deg()); } template auto inv(suisen::FPSNaive a) -> decltype(mint::mod(), suisen::FPSNaive{}) { return a.inv(suisen::FPSNaive::MAX_DEG == std::numeric_limits::max() / 2 ? suisen::FPSNaive::MAX_DEG : a.deg()); } namespace suisen { template using convolution_t = std::vector(*)(const std::vector&, const std::vector&); template struct FPS : public std::vector { using base_type = std::vector; using value_type = typename base_type::value_type; using base_type::vector; FPS(const std::initializer_list l) : std::vector::vector(l) {} FPS(const std::vector& v) : std::vector::vector(v) {} FPS(std::vector&& v) : std::vector::vector(std::move(v)) {} static void set_multiplication(convolution_t multiplication) { FPS::mult = multiplication; } int size() const noexcept { return base_type::size(); } int deg() const noexcept { return size() - 1; } void ensure(int n) { if (size() < n) this->resize(n); } value_type safe_get(int d) const { return d <= deg() ? (*this)[d] : 0; } value_type& safe_get(int d) { ensure(d + 1); return (*this)[d]; } int cut_trailing_zeros() { while (this->size() and this->back() == 0) this->pop_back(); return deg(); } void cut(int n) { if (size() > n) this->resize(std::max(0, n)); } FPS cut_copy(int n) const { FPS res(this->begin(), this->begin() + std::min(size(), n)); res.ensure(n); return res; } /* Unary Operations */ FPS operator+() const { return *this; } FPS operator-() const { FPS res = *this; for (auto& e : res) e = -e; return res; } FPS& operator++() { return ++safe_get(0), * this; } FPS& operator--() { return --safe_get(0), * this; } FPS operator++(int) { FPS res = *this; ++(*this); return res; } FPS operator--(int) { FPS res = *this; --(*this); return res; } /* Binary Operations With Constant */ FPS& operator+=(const value_type& x) { return safe_get(0) += x, *this; } FPS& operator-=(const value_type& x) { return safe_get(0) -= x, *this; } FPS& operator*=(const value_type& x) { for (auto& e : *this) e *= x; return *this; } FPS& operator/=(const value_type& x) { return *this *= x.inv(); } friend FPS operator+(FPS f, const value_type& x) { f += x; return f; } friend FPS operator+(const value_type& x, FPS f) { f += x; return f; } friend FPS operator-(FPS f, const value_type& x) { f -= x; return f; } friend FPS operator-(const value_type& x, FPS f) { f -= x; return -f; } friend FPS operator*(FPS f, const value_type& x) { f *= x; return f; } friend FPS operator*(const value_type& x, FPS f) { f *= x; return f; } friend FPS operator/(FPS f, const value_type& x) { f /= x; return f; } /* Binary Operations With Formal Power Series */ FPS& operator+=(const FPS& g) { const int n = g.size(); ensure(n); for (int i = 0; i < n; ++i) (*this)[i] += g[i]; return *this; } FPS& operator-=(const FPS& g) { const int n = g.size(); ensure(n); for (int i = 0; i < n; ++i) (*this)[i] -= g[i]; return *this; } FPS& operator*=(const FPS& g) { return *this = *this * g; } FPS& operator/=(const FPS& g) { return *this = *this / g; } FPS& operator%=(const FPS& g) { return *this = *this % g; } friend FPS operator+(FPS f, const FPS& g) { f += g; return f; } friend FPS operator-(FPS f, const FPS& g) { f -= g; return f; } friend FPS operator*(const FPS& f, const FPS& g) { return mult(f, g); } friend FPS operator/(FPS f, FPS g) { if (f.size() < 60) return FPSNaive(f).div_mod(g).first; f.cut_trailing_zeros(), g.cut_trailing_zeros(); const int fd = f.deg(), gd = g.deg(); assert(gd >= 0); if (fd < gd) return {}; if (gd == 0) { f /= g[0]; return f; } std::reverse(f.begin(), f.end()), std::reverse(g.begin(), g.end()); const int qd = fd - gd; FPS q = f * g.inv(qd + 1); q.cut(qd + 1); std::reverse(q.begin(), q.end()); return q; } friend FPS operator%(const FPS& f, const FPS& g) { return f.div_mod(g).second; } std::pair div_mod(const FPS& g) const { if (size() < 60) { auto [q, r] = FPSNaive(*this).div_mod(g); return { q, r }; } FPS q = *this / g, r = *this - g * q; r.cut_trailing_zeros(); return { q, r }; } /* Shift Operations */ FPS& operator<<=(const int shamt) { return this->insert(this->begin(), shamt, 0), * this; } FPS& operator>>=(const int shamt) { return this->erase(this->begin(), this->begin() + std::min(shamt, size())), * this; } friend FPS operator<<(FPS f, const int shamt) { f <<= shamt; return f; } friend FPS operator>>(FPS f, const int shamt) { f >>= shamt; return f; } /* Compare */ friend bool operator==(const FPS& f, const FPS& g) { const int n = f.size(), m = g.size(); if (n < m) return g == f; for (int i = 0; i < m; ++i) if (f[i] != g[i]) return false; for (int i = m; i < n; ++i) if (f[i] != 0) return false; return true; } friend bool operator!=(const FPS& f, const FPS& g) { return not (f == g); } /* Other Operations */ FPS& diff_inplace() { const int n = size(); for (int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i; return (*this)[n - 1] = 0, *this; } FPS diff() const { FPS res = *this; res.diff_inplace(); return res; } FPS& intg_inplace() { const int n = size(); inv_mods invs(n); this->resize(n + 1); for (int i = n; i > 0; --i) (*this)[i] = (*this)[i - 1] * invs[i]; return (*this)[0] = 0, *this; } FPS intg() const { FPS res = *this; res.intg_inplace(); return res; } FPS& inv_inplace(const int n = -1) { return *this = inv(n); } FPS inv(int n = -1) const { if (n < 0) n = size(); if (n < 60) return FPSNaive(*this).inv(); if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return inv_sparse(std::move(*sp_f), n); FPS res{ (*this)[0].inv() }; for (int k = 1; k < n; k *= 2) { FPS tmp(cut_copy(k * 2) * (res * res)); tmp.resize(2 * k); res = 2 * res - tmp; } res.resize(n); return res; } FPS& log_inplace(int n = -1) { return *this = log(n); } FPS log(int n = -1) const { assert(safe_get(0) == 1); if (n < 0) n = size(); if (n < 60) return FPSNaive(cut_copy(n)).log(); if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return log_sparse(std::move(*sp_f), n); FPS res = inv(n) * diff(); res.resize(n - 1); return res.intg(); } FPS& exp_inplace(int n = -1) { return *this = exp(n); } FPS exp(int n = -1) { assert(safe_get(0) == 0); if (n < 0) n = size(); if (n < 60) return FPSNaive(cut_copy(n)).exp(); if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return exp_sparse(std::move(*sp_f), n); FPS res{ 1 }; for (int k = 1; k < n; k *= 2) res *= ++(cut_copy(k * 2) - res.log(k * 2)), res.cut(k * 2); res.resize(n); return res; } FPS& pow_inplace(long long k, int n = -1) { return *this = pow(k, n); } FPS pow(const long long k, int n = -1) const { if (n < 0) n = size(); if (n < 60) return FPSNaive(cut_copy(n)).pow(k); if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return pow_sparse(std::move(*sp_f), k, n); if (k == 0) { FPS f{ 1 }; f.resize(n); return f; } int tlz = 0; while (tlz < size() and (*this)[tlz] == 0) ++tlz; if (tlz == size() or tlz > (n - 1) / k) return FPS(n, 0); const int m = n - tlz * k; FPS f = *this >> tlz; value_type base = f[0]; return ((((f /= base).log(m) *= k).exp(m) *= base.pow(k)) <<= (tlz * k)); } std::optional safe_sqrt(int n = -1) const { if (n < 0) n = size(); if (n < 60) return FPSNaive(cut_copy(n)).safe_sqrt(); if (auto sp_f = sparse_fps_format(15); sp_f.has_value()) return safe_sqrt_sparse(std::move(*sp_f), n); int tlz = 0; while (tlz < size() and (*this)[tlz] == 0) ++tlz; if (tlz == size()) return FPS(n, 0); if (tlz & 1) return std::nullopt; const int m = n - tlz / 2; FPS h(this->begin() + tlz, this->end()); auto q0 = ::safe_sqrt(h[0]); if (not q0.has_value()) return std::nullopt; FPS res{ *q0 }; mint inv_2 = mint(2).inv(); for (int k = 1; k < m; k *= 2) { FPS tmp = h.cut_copy(k * 2) * res.inv(2 * k); tmp.cut(2 * k); res += tmp, res *= inv_2; } res.resize(m); res <<= tlz / 2; return res; } FPS& sqrt_inplace(int n = -1) { return *this = sqrt(n); } FPS sqrt(int n = -1) const { return *safe_sqrt(n); } mint eval(mint x) const { mint y = 0; for (int i = size() - 1; i >= 0; --i) y = y * x + (*this)[i]; return y; } static FPS prod(const std::vector& fs) { auto comp = [](const FPS& f, const FPS& g) { return f.size() > g.size(); }; std::priority_queue, decltype(comp)> pq{ comp }; for (const auto& f : fs) pq.push(f); while (pq.size() > 1) { auto f = pq.top(); pq.pop(); auto g = pq.top(); pq.pop(); pq.push(f * g); } return pq.top(); } protected: static convolution_t mult; std::optional>> sparse_fps_format(int max_size) const { std::vector> res; for (int i = 0; i <= deg() and int(res.size()) <= max_size; ++i) if (value_type v = (*this)[i]; v != 0) res.emplace_back(i, v); if (int(res.size()) > max_size) return std::nullopt; return res; } static FPS div_fps_sparse(const FPS& f, const std::vector>& g, int n) { const int siz = g.size(); assert(siz and g[0].first == 0); const value_type inv_g0 = g[0].second.inv(); FPS h(n); for (int i = 0; i < n; ++i) { value_type v = f.safe_get(i); for (int idx = 1; idx < siz; ++idx) { const auto& [j, gj] = g[idx]; if (j > i) break; v -= gj * h[i - j]; } h[i] = v * inv_g0; } return h; } static FPS inv_sparse(const std::vector>& g, const int n) { return div_fps_sparse(FPS{ 1 }, g, n); } static FPS exp_sparse(const std::vector>& f, const int n) { const int siz = f.size(); assert(not siz or f[0].first != 0); FPS g(n); g[0] = 1; inv_mods invs(n); for (int i = 1; i < n; ++i) { value_type v = 0; for (const auto& [j, fj] : f) { if (j > i) break; v += j * fj * g[i - j]; } v *= invs[i]; g[i] = v; } return g; } static FPS log_sparse(const std::vector>& f, const int n) { const int siz = f.size(); assert(siz and f[0].first == 0 and f[0].second == 1); FPS g(n); for (int idx = 1; idx < siz; ++idx) { const auto& [j, fj] = f[idx]; if (j >= n) break; g[j] = j * fj; } inv_mods invs(n); for (int i = 1; i < n; ++i) { value_type v = g[i]; for (int idx = 1; idx < siz; ++idx) { const auto& [j, fj] = f[idx]; if (j > i) break; v -= fj * g[i - j] * (i - j); } v *= invs[i]; g[i] = v; } return g; } static FPS pow_sparse(const std::vector>& f, const long long k, const int n) { if (k == 0) { FPS res(n, 0); res[0] = 1; return res; } const int siz = f.size(); if (not siz) return FPS(n, 0); const int p = f[0].first; if (p > (n - 1) / k) return FPS(n, 0); const value_type inv_f0 = f[0].second.inv(); const int lz = p * k; FPS g(n); g[lz] = f[0].second.pow(k); inv_mods invs(n); for (int i = 1; lz + i < n; ++i) { value_type v = 0; for (int idx = 1; idx < siz; ++idx) { auto [j, fj] = f[idx]; j -= p; if (j > i) break; v += fj * g[lz + i - j] * (value_type(k) * j - (i - j)); } v *= invs[i] * inv_f0; g[lz + i] = v; } return g; } static std::optional safe_sqrt_sparse(const std::vector>& f, const int n) { const int siz = f.size(); if (not siz) return FPS(n, 0); const int p = f[0].first; if (p % 2 == 1) return std::nullopt; if (p / 2 >= n) return FPS(n, 0); const value_type inv_f0 = f[0].second.inv(); const int lz = p / 2; FPS g(n); auto opt_g0 = ::safe_sqrt(f[0].second); if (not opt_g0.has_value()) return std::nullopt; g[lz] = *opt_g0; value_type k = mint(2).inv(); inv_mods invs(n); for (int i = 1; lz + i < n; ++i) { value_type v = 0; for (int idx = 1; idx < siz; ++idx) { auto [j, fj] = f[idx]; j -= p; if (j > i) break; v += fj * g[lz + i - j] * (k * j - (i - j)); } v *= invs[i] * inv_f0; g[lz + i] = v; } return g; } static FPS sqrt_sparse(const std::vector>& f, const int n) { return *safe_sqrt(f, n); } }; template convolution_t FPS::mult = [](const auto&, const auto&) { std::cerr << "convolution function is not available." << std::endl; assert(false); return std::vector{}; }; } // namespace suisen template suisen::FPS sqrt(suisen::FPS a) { return a.sqrt(); } template suisen::FPS log(suisen::FPS a) { return a.log(); } template suisen::FPS exp(suisen::FPS a) { return a.exp(); } template suisen::FPS pow(suisen::FPS a, T b) { return a.pow(b); } template suisen::FPS inv(suisen::FPS a) { return a.inv(); } namespace suisen { template struct factorial { factorial() {} factorial(int n) { ensure(n); } static void ensure(const int n) { int sz = _fac.size(); if (n + 1 <= sz) return; int new_size = std::max(n + 1, sz * 2); _fac.resize(new_size), _fac_inv.resize(new_size); for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i; _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1]; for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i; } T fac(const int i) { ensure(i); return _fac[i]; } T operator()(int i) { return fac(i); } U fac_inv(const int i) { ensure(i); return _fac_inv[i]; } U binom(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[r] * _fac_inv[n - r]; } U perm(const int n, const int r) { if (n < 0 or r < 0 or n < r) return 0; ensure(n); return _fac[n] * _fac_inv[n - r]; } private: static std::vector _fac; static std::vector _fac_inv; }; template std::vector factorial::_fac{ 1 }; template std::vector factorial::_fac_inv{ 1 }; } // namespace suisen #include #include namespace suisen { // referece: https://37zigen.com/linear-sieve/ class LinearSieve { public: LinearSieve(const int n) : _n(n), min_prime_factor(std::vector(n + 1)) { std::iota(min_prime_factor.begin(), min_prime_factor.end(), 0); prime_list.reserve(_n / 20); for (int d = 2; d <= _n; ++d) { if (min_prime_factor[d] == d) prime_list.push_back(d); const int prime_max = std::min(min_prime_factor[d], _n / d); for (int prime : prime_list) { if (prime > prime_max) break; min_prime_factor[prime * d] = prime; } } } int prime_num() const noexcept { return prime_list.size(); } /** * Returns a vector of primes in [0, n]. * It is guaranteed that the returned vector is sorted in ascending order. */ const std::vector& get_prime_list() const noexcept { return prime_list; } const std::vector& get_min_prime_factor() const noexcept { return min_prime_factor; } /** * Returns a vector of `{ prime, index }`. * It is guaranteed that the returned vector is sorted in ascending order. */ std::vector> factorize(int n) const noexcept { assert(0 < n and n <= _n); std::vector> prime_powers; while (n > 1) { int p = min_prime_factor[n], c = 0; do { n /= p, ++c; } while (n % p == 0); prime_powers.emplace_back(p, c); } return prime_powers; } private: const int _n; std::vector min_prime_factor; std::vector prime_list; }; } // namespace suisen namespace suisen { // returns { 0^k, 1^k, ..., n^k } template std::vector powers(uint32_t n, uint64_t k) { const auto mpf = LinearSieve(n).get_min_prime_factor(); std::vector res(n + 1); res[0] = k == 0; for (uint32_t i = 1; i <= n; ++i) res[i] = i == 1 ? 1 : uint32_t(mpf[i]) == i ? mint(i).pow(k) : res[mpf[i]] * res[i / mpf[i]]; return res; } } // namespace suisen // reference: https://en.wikipedia.org/wiki/Eulerian_number namespace suisen { template std::vector eulerian_number(uint32_t n) { using mint = typename FPSType::value_type; if (n == 0) return {}; factorial fac(n + 1); const uint32_t h = (n + 1) >> 1; FPSType f = powers(h, n); f.erase(f.begin()); FPSType g(h); for (uint32_t i = 0; i < h; ++i) { mint v = fac.binom(n + 1, i); g[i] = i & 1 ? -v : v; } FPSType res = f * g; res.resize(n); for (uint32_t i = h; i < n; ++i) res[i] = res[n - 1 - i]; return res; } template std::vector> eulerian_number_table(uint32_t n) { if (n == 0) return {}; std::vector dp(n + 1, std::vector{}); for (uint32_t i = 1; i <= n; ++i) { dp[i].resize(i); dp[i][0] = dp[i][i - 1] = 1; for (uint32_t j = 1; j < i - 1; ++j) dp[i][j] = (i - j) * dp[i - 1][j - 1] + (j + 1) * dp[i - 1][j]; } return dp; } } // namespace suisen /** * [Idea] reference : https://motsu-xe.hatenablog.com/entry/2021/05/13/224016 * * SWAG + simulate a deque with 2 stacks * * [Operations] reference : https://www.slideshare.net/catupper/amortize-analysis-of-deque-with-2-stack * * `l`, `r` is a stack of { value, sum } * * accumulate * <---------- ------> fold values from inside * ( l ][ r ) * * pop_front: * 1. `l` is not empty * ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1) * 2. `l` is empty * (][ r ) -> ( l ][ r ) # split `r` at its middle point. amortized O(1) * ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1) * * pop_back: * 1. `r` is not empty * ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1) * 2. `r` is empty * ( l ][) -> ( l ][ r ) # split `l` at its middle point. amortized O(1) * ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1) * * push_front: * ( l ][ r ) -> ( l ][ r ) # push to `l`. O(1) * * push_back: * ( l ][ r ) -> ( l ][ r ) # push to `r`. O(1) */ namespace suisen { template struct DequeAggregation { struct DequeAggregationIterator { using difference_type = int; using value_type = T; using pointer = value_type*; using reference = value_type&; using iterator_category = std::random_access_iterator_tag; using fi_iterator_type = typename std::vector>::const_reverse_iterator; using se_iterator_type = typename std::vector>::const_iterator; fi_iterator_type it_l; fi_iterator_type it_l_end; se_iterator_type it_r_begin; se_iterator_type it_r; DequeAggregationIterator& operator++() { if (it_l == it_l_end) ++it_r; else ++it_l; return *this; } DequeAggregationIterator operator++(int) { DequeAggregationIterator ret = *this; ++(*this); return ret; } DequeAggregationIterator& operator--() { if (it_r == it_r_begin) --it_l; else --it_r; return *this; } DequeAggregationIterator operator--(int) { DequeAggregationIterator ret = *this; --(*this); return ret; } DequeAggregationIterator& operator+=(difference_type dif) { if (dif < 0) return *this -= -dif; if (int d = it_l_end - it_l; d < dif) it_l = it_l_end, it_r += dif - d; else it_l += dif; return *this; } friend DequeAggregationIterator operator+(DequeAggregationIterator it, difference_type dif) { it += dif; return it; } friend DequeAggregationIterator operator+(difference_type dif, DequeAggregationIterator it) { it += dif; return it; } DequeAggregationIterator& operator-=(difference_type dif) { if (dif < 0) return *this += -dif; if (int d = it_r - it_r_begin; d < dif) it_r = it_r_begin, it_l -= dif - d; else it_r -= dif; return *this; } friend DequeAggregationIterator operator-(DequeAggregationIterator it, difference_type dif) { it -= dif; return it; } difference_type operator-(const DequeAggregationIterator &rhs) const { difference_type d1 = it_l == it_l_end ? it_r - it_r_begin : it_l - it_l_end; difference_type d2 = rhs.it_l == rhs.it_l_end ? rhs.it_r - rhs.it_r_begin : rhs.it_l - rhs.it_l_end; return d1 - d2; } const value_type& operator[](difference_type i) const { return *((*this) + i); } const value_type& operator*() const { return it_l == it_l_end ? it_r->first : it_l->first; } bool operator!=(const DequeAggregationIterator &rhs) const { return it_l != rhs.it_l or it_r != rhs.it_r; } bool operator==(const DequeAggregationIterator &rhs) const { return not (*this != rhs); } bool operator< (const DequeAggregationIterator &rhs) const { return (*this) - rhs < 0; } bool operator<=(const DequeAggregationIterator &rhs) const { return (*this) - rhs <= 0; } bool operator> (const DequeAggregationIterator &rhs) const { return (*this) - rhs > 0; } bool operator>=(const DequeAggregationIterator &rhs) const { return (*this) - rhs >= 0; } }; using iterator = DequeAggregationIterator; using difference_type = typename iterator::difference_type; using value_type = typename iterator::value_type; using pointer = typename iterator::pointer; using reference = typename iterator::reference; DequeAggregation() = default; template , std::nullptr_t> = nullptr> DequeAggregation(InputIterator first, InputIterator last) { for (; first != last; ++first) push_back(*first); } template , std::nullptr_t> = nullptr> DequeAggregation(const Container &c) : DequeAggregation(std::begin(c), std::end(c)) {} value_type prod() const { return op(prod(_st_l), prod(_st_r)); } void push_back(const value_type &val) { _st_r.emplace_back(val, op(prod(_st_r), val)); } void push_front(const value_type &val) { _st_l.emplace_back(val, op(val, prod(_st_l))); } void pop_back() { if (_st_r.size()) return _st_r.pop_back(); const int siz = _st_l.size(); const int l = siz >> 1, r = siz - l; assert(r); // <=> siz > 0 for (int i = r - 1; i > 0; --i) push_back(std::move(_st_l[i].first)); _st_l.erase(_st_l.begin(), _st_l.begin() + r); if (l == 0) return; _st_l[0].second = _st_l[0].first; for (int i = 1; i < l; ++i) _st_l[i].second = op(_st_l[i].first, _st_l[i - 1].second); } void pop_front() { if (_st_l.size()) return _st_l.pop_back(); const int siz = _st_r.size(); const int r = siz >> 1, l = siz - r; assert(l); // <=> siz > 0 for (int i = l - 1; i > 0; --i) push_front(std::move(_st_r[i].first)); _st_r.erase(_st_r.begin(), _st_r.begin() + l); if (r == 0) return; _st_r[0].second = _st_r[0].first; for (int i = 1; i < r; ++i) _st_r[i].second = op(_st_r[i - 1].second, _st_r[i].first); } const value_type& front() const { return _st_l.size() ? _st_l.back().first : _st_r.front().first; } const value_type& back() const { return _st_r.size() ? _st_r.back().first : _st_l.front().first; } const value_type& operator[](int i) const { const int k = i - _st_l.size(); return k < 0 ? _st_l[~k].first : _st_r[k].first; } int size() const { return _st_l.size() + _st_r.size(); } void clear() { _st_l.clear(), _st_r.clear(); } void shrink_to_fit() { _st_l.shrink_to_fit(), _st_r.shrink_to_fit(); } iterator begin() const { return iterator { _st_l.rbegin(), _st_l.rend(), _st_r.begin(), _st_r.begin() }; } iterator end() const { return iterator { _st_l.rend(), _st_l.rend(), _st_r.begin(), _st_r.end() }; } iterator cbegin() const { return begin(); } iterator cend() const { return end(); } private: std::vector> _st_l, _st_r; value_type prod(const std::vector> &st) const { return st.empty() ? e() : st.back().second; } }; } // namespace suisen mint op(mint x, mint y) { return x * y; } mint e() { return 1; } constexpr uint32_t K_MAX = 5000; int main() { suisen::FPS::set_multiplication([](const auto &a, const auto &b) { return atcoder::convolution(a, b); }); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); uint32_t n; uint64_t m; std::cin >> n >> m; std::vector c(K_MAX + 1); for (uint32_t i = 0; i < n; ++i) { uint32_t k; std::cin >> k; ++c[k]; } suisen::factorial fac(n + K_MAX); mint ans = 0; suisen::DequeAggregation dq; for (uint32_t d = 0; d < n; ++d) dq.push_front(m + d); for (uint32_t k = 1; k <= K_MAX; ++k) { std::vector e = suisen::eulerian_number>(k); dq.push_front(m + n + k - 1); mint sum = 0; const uint32_t p = std::min(uint64_t(k), m); for (uint32_t i = 0; i < p; ++i) { sum += e[i] * dq.prod(); dq.pop_front(); dq.push_back(m - i - 1); } ans += c[k] * sum * fac.fac_inv(n + k); for (uint32_t i = p; i --> 0;) { dq.push_front(m - i + n + k - 1); dq.pop_back(); } } std::cout << ans.val() << std::endl; return 0; }