結果
問題 | No.1510 Simple Integral |
ユーザー |
|
提出日時 | 2025-01-06 21:51:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 59,306 bytes |
コンパイル時間 | 3,097 ms |
コンパイル使用メモリ | 180,192 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-06 21:51:24 |
合計ジャッジ時間 | 4,516 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#ifndef KK2_TEMPLATE_PROCON_HPP#define KK2_TEMPLATE_PROCON_HPP 1#include <algorithm>#include <array>#include <bitset>#include <cassert>// #include <chrono>// #include <cmath>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <map>#include <numeric>#include <optional>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#ifndef KK2_TEMPLATE_CONSTANT_HPP#define KK2_TEMPLATE_CONSTANT_HPP 1#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1#include <functional>#include <queue>#include <utility>#include <vector>using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;using pi = std::pair<int, int>;using pl = std::pair<i64, i64>;using pil = std::pair<int, i64>;using pli = std::pair<i64, int>;template <class T> using vc = std::vector<T>;template <class T> using vvc = std::vector<vc<T>>;template <class T> using vvvc = std::vector<vvc<T>>;template <class T> using vvvvc = std::vector<vvvc<T>>;template <class T> using pq = std::priority_queue<T>;template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP// #include "type_alias.hpp"template <class T> constexpr T infty = 0;template <> constexpr int infty<int> = (1 << 30) - 123;template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);template <> constexpr u32 infty<u32> = infty<int>;template <> constexpr u64 infty<u64> = infty<i64>;template <> constexpr u128 infty<u128> = infty<i128>;template <> constexpr double infty<double> = infty<i64>;template <> constexpr long double infty<long double> = infty<i64>;constexpr int mod = 998244353;constexpr int modu = 1e9 + 7;constexpr long double PI = 3.14159265358979323846;#endif // KK2_TEMPLATE_CONSTANT_HPP// #include "constant.hpp"#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1#include <algorithm>#include <vector>namespace kk2 {template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {if constexpr (sizeof...(sizes) == 0) {return std::vector<T>(first);} else {return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));}}template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {std::fill(std::begin(v), std::end(v), T(x));}template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {for (auto &u : v) fill_all(u, x);}template <class C> int mysize(const C &c) {return c.size();}} // namespace kk2template <class T, class S> inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S> inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP// #include "function_util.hpp"#ifndef KK2_TEMPLATE_IO_UTIL_HPP#define KK2_TEMPLATE_IO_UTIL_HPP 1#include <array>#include <utility>#include <vector>#ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP#define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1#include <istream>#include <ostream>#include <type_traits>namespace kk2 {#ifndef _MSC_VERtemplate <typename T>using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::valueor std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <typename T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::valueor std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <typename T>using is_integral =typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::valueor is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_unsigned =typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;template <typename T>using to_unsigned =typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;#elsetemplate <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;template <typename T> using to_unsigned = std::make_unsigned<T>;#endif // _MSC_VERtemplate <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;template <typename T>using is_function_pointer =typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,std::true_type,std::false_type>::type;template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>struct is_two_args_function_pointer : std::false_type {};template <typename R, typename T1, typename T2>struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};template <typename T>using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;namespace type_traits {struct istream_tag {};struct ostream_tag {};} // namespace type_traitstemplate <typename T>using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value|| std::is_same<T, std::ifstream>::value,std::true_type,std::false_type>::type;template <typename T>using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value|| std::is_same<T, std::ofstream>::value,std::true_type,std::false_type>::type;template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;template <typename T>using is_istream =typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_ostream =typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,std::true_type,std::false_type>::type;template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;} // namespace kk2#endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP// #include "../type_traits/type_traits.hpp"// なんかoj verifyはプロトタイプ宣言が落ちるnamespace impl {struct read {template <class IStream, class T> static void all_read(IStream &is, T &x) { is >> x; }template <class IStream, class T, class U>static void all_read(IStream &is, std::pair<T, U> &p) {all_read(is, p.first);all_read(is, p.second);}template <class IStream, class T> static void all_read(IStream &is, std::vector<T> &v) {for (T &x : v) all_read(is, x);}template <class IStream, class T, size_t F>static void all_read(IStream &is, std::array<T, F> &a) {for (T &x : a) all_read(is, x);}};struct write {template <class OStream, class T> static void all_write(OStream &os, const T &x) { os << x; }template <class OStream, class T, class U>static void all_write(OStream &os, const std::pair<T, U> &p) {all_write(os, p.first);all_write(os, ' ');all_write(os, p.second);}template <class OStream, class T> static void all_write(OStream &os, const std::vector<T> &v) {for (int i = 0; i < (int)v.size(); ++i) {if (i) all_write(os, ' ');all_write(os, v[i]);}}template <class OStream, class T, size_t F>static void all_write(OStream &os, const std::array<T, F> &a) {for (int i = 0; i < (int)F; ++i) {if (i) all_write(os, ' ');all_write(os, a[i]);}}};} // namespace impltemplate <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>IStream &operator>>(IStream &is, std::pair<T, U> &p) {impl::read::all_read(is, p);return is;}template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>IStream &operator>>(IStream &is, std::vector<T> &v) {impl::read::all_read(is, v);return is;}template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>IStream &operator>>(IStream &is, std::array<T, F> &a) {impl::read::all_read(is, a);return is;}template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>OStream &operator<<(OStream &os, const std::pair<T, U> &p) {impl::write::all_write(os, p);return os;}template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>OStream &operator<<(OStream &os, const std::vector<T> &v) {impl::write::all_write(os, v);return os;}template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>OStream &operator<<(OStream &os, const std::array<T, F> &a) {impl::write::all_write(os, a);return os;}#endif // KK2_TEMPLATE_IO_UTIL_HPP// #include "io_util.hpp"#ifndef KK2_TEMPLATE_MACROS_HPP#define KK2_TEMPLATE_MACROS_HPP 1#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)#define overload3(a, b, c, d, ...) d#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)#define fi first#define se second#define all(p) p.begin(), p.end()#endif // KK2_TEMPLATE_MACROS_HPP// #include "macros.hpp"// #include "type_alias.hpp"struct FastIOSetUp {FastIOSetUp() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} fast_io_set_up;auto &kin = std::cin;auto &kout = std::cout;auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;void Yes(bool b = 1) {kout << (b ? "Yes\n" : "No\n");}void No(bool b = 1) {kout << (b ? "No\n" : "Yes\n");}void YES(bool b = 1) {kout << (b ? "YES\n" : "NO\n");}void NO(bool b = 1) {kout << (b ? "NO\n" : "YES\n");}void yes(bool b = 1) {kout << (b ? "yes\n" : "no\n");}void no(bool b = 1) {kout << (b ? "no\n" : "yes\n");}std::istream &operator>>(std::istream &is, u128 &x) {std::string s;is >> s;x = 0;for (char c : s) {assert('0' <= c && c <= '9');x = x * 10 + c - '0';}return is;}std::istream &operator>>(std::istream &is, i128 &x) {std::string s;is >> s;bool neg = s[0] == '-';x = 0;for (int i = neg; i < (int)s.size(); i++) {assert('0' <= s[i] && s[i] <= '9');x = x * 10 + s[i] - '0';}if (neg) x = -x;return is;}std::ostream &operator<<(std::ostream &os, u128 x) {if (x == 0) return os << '0';std::string s;while (x) {s.push_back('0' + x % 10);x /= 10;}std::reverse(s.begin(), s.end());return os << s;}std::ostream &operator<<(std::ostream &os, i128 x) {if (x == 0) return os << '0';if (x < 0) {os << '-';x = -x;}std::string s;while (x) {s.push_back('0' + x % 10);x /= 10;}std::reverse(s.begin(), s.end());return os << s;}#endif // KK2_TEMPLATE_PROCON_HPP// #include <kk2/template/procon.hpp>#ifndef KK2_TEMPLATE_DEBUG_HPP#define KK2_TEMPLATE_DEBUG_HPP 1#include <array>#include <deque>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#ifndef KK2_TYPE_TRAITS_MEMBER_HPP#define KK2_TYPE_TRAITS_MEMBER_HPP 1#include <type_traits>namespace kk2 {#define HAS_MEMBER_FUNC(member) \template <typename T, typename... Ts> struct has_member_func_##member##_impl { \template <typename U> \static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *); \template <typename U> static std::false_type check(...); \using type = decltype(check<T>(nullptr)); \}; \template <typename T, typename... Ts> \struct has_member_func_##member : has_member_func_##member##_impl<T, Ts...>::type {}; \template <typename T, typename... Ts> \using has_member_func_##member##_t = \std::enable_if_t<has_member_func_##member<T, Ts...>::value>; \template <typename T, typename... Ts> \using not_has_member_func_##member##_t = \std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;#define HAS_MEMBER_VAR(member) \template <typename T> struct has_member_var_##member##_impl { \template <typename U> static std::true_type check(decltype(std::declval<U>().member) *); \template <typename U> static std::false_type check(...); \using type = decltype(check<T>(nullptr)); \}; \template <typename T> \struct has_member_var_##member : has_member_var_##member##_impl<T>::type {}; \template <typename T> \using has_member_var_##member##_t = std::enable_if_t<has_member_var_##member<T>::value>; \template <typename T> \using not_has_member_var_##member##_t = std::enable_if_t<!has_member_var_##member<T>::value>;HAS_MEMBER_FUNC(debug_output)#undef HAS_MEMBER_FUNC#undef HAS_MEMBER_VAR} // namespace kk2#endif // KK2_TYPE_TRAITS_MEMBER_HPP// #include "../type_traits/member.hpp"// #include "../type_traits/type_traits.hpp"namespace kk2 {namespace debug {#ifdef KK2template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);template <class OStream, class T, is_ostream_t<OStream> *>void output(OStream &os, const std::vector<T> &v);template <class OStream, class T, size_t F, is_ostream_t<OStream> *>void output(OStream &os, const std::array<T, F> &a);template <class OStream, class T, class U, is_ostream_t<OStream> *>void output(OStream &os, const std::pair<T, U> &p);template <class OStream, class T, is_ostream_t<OStream> *>void output(OStream &os, const std::queue<T> &q);template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);template <class OStream, class T, is_ostream_t<OStream> *>void output(OStream &os, const std::deque<T> &d);template <class OStream, class T, is_ostream_t<OStream> *>void output(OStream &os, const std::stack<T> &s);template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>void output(OStream &os, const std::set<Key, Compare, Allocator> &s);template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);template <class OStream,class Key,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> *>void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);template <class OStream,class Key,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> *>void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);template <class OStream,class Key,class T,class Compare,class Allocator,is_ostream_t<OStream> *>void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);template <class OStream,class Key,class T,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> *>void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {}template <class OStream, class T, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const T &t) {if constexpr (has_member_func_debug_output<T, OStream &>::value) {t.debug_output(os);} else {os << t;}}template <class OStream, class T, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::vector<T> &v) {os << "[";for (int i = 0; i < (int)v.size(); i++) {output(os, v[i]);if (i + 1 != (int)v.size()) os << ", ";}os << "]";}template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::array<T, F> &a) {os << "[";for (int i = 0; i < (int)F; i++) {output(os, a[i]);if (i + 1 != (int)F) os << ", ";}os << "]";}template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::pair<T, U> &p) {os << "(";output(os, p.first);os << ", ";output(os, p.second);os << ")";}template <class OStream, class T, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::queue<T> &q) {os << "[";std::queue<T> tmp = q;while (!tmp.empty()) {output(os, tmp.front());tmp.pop();if (!tmp.empty()) os << ", ";}os << "]";}template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {os << "[";std::priority_queue<T, Container, Compare> tmp = q;while (!tmp.empty()) {output(os, tmp.top());tmp.pop();if (!tmp.empty()) os << ", ";}os << "]";}template <class OStream, class T, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::deque<T> &d) {os << "[";std::deque<T> tmp = d;while (!tmp.empty()) {output(os, tmp.front());tmp.pop_front();if (!tmp.empty()) os << ", ";}os << "]";}template <class OStream, class T, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::stack<T> &s) {os << "[";std::stack<T> tmp = s;std::vector<T> v;while (!tmp.empty()) {v.push_back(tmp.top());tmp.pop();}for (int i = (int)v.size() - 1; i >= 0; i--) {output(os, v[i]);if (i != 0) os << ", ";}os << "]";}template <class OStream,class Key,class Compare,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {os << "{";std::set<Key, Compare, Allocator> tmp = s;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, *it);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream,class Key,class Compare,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {os << "{";std::multiset<Key, Compare, Allocator> tmp = s;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, *it);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream,class Key,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {os << "{";std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, *it);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream,class Key,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {os << "{";std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, *it);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream,class Key,class T,class Compare,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {os << "{";std::map<Key, T, Compare, Allocator> tmp = m;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, it->first);os << ": ";output(os, it->second);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream,class Key,class T,class Hash,class KeyEqual,class Allocator,is_ostream_t<OStream> * = nullptr>void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {os << "{";std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;for (auto it = tmp.begin(); it != tmp.end(); ++it) {output(os, it->first);os << ": ";output(os, it->second);if (std::next(it) != tmp.end()) os << ", ";}os << "}";}template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>void output(OStream &os, const T &t, const Args &...args) {output(os, t);os << ' ';output(os, args...);}template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {os << '\n';os.flush();}template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>void outputln(OStream &os, const T &t, const Args &...args) {output(os, t, args...);os << '\n';os.flush();}#elsetemplate <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>void output(OStream &, const Args &...) {}template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>void outputln(OStream &, const Args &...) {}#endif // KK2} // namespace debug} // namespace kk2#endif // KK2_TEMPLATE_DEBUG_HPP// #include <kk2/template/debug.hpp>#ifndef KK2_FPS_NTT_FRIENDLY_HPP#define KK2_FPS_NTT_FRIENDLY_HPP 1#ifndef KK2_CONVOLUTION_CONVOLUTION_HPP#define KK2_CONVOLUTION_CONVOLUTION_HPP 1#include <algorithm>#include <vector>#ifndef KK2_MATH_MOD_BUTTERFLY_HPP#define KK2_MATH_MOD_BUTTERFLY_HPP 1#include <algorithm>#ifndef KK2_MATH_MOD_PRIMITIVE_ROOT_HPP#define KK2_MATH_MOD_PRIMITIVE_ROOT_HPP 1#ifndef KK2_MATH_MOD_POW_MOD_HPP#define KK2_MATH_MOD_POW_MOD_HPP 1#include <cassert>// #include "../type_traits/type_traits.hpp"namespace kk2 {template <class S, class T, class U> constexpr S pow_mod(T x, U n, T m) {assert(n >= 0);if (m == 1) return S(0);S _m = m, r = 1;S y = x % _m;if (y < 0) y += _m;while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}} // namespace kk2#endif // KK2_MATH_MOD_POW_MOD_HPP// #include "pow_mod.hpp"namespace kk2 {constexpr int primitive_root_constexpr(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;if (m == 1107296257) return 10;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long long)(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<long long>(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}template <int m> static constexpr int primitive_root = primitive_root_constexpr(m);} // namespace kk2#endif // KK2_MATH_MOD_PRIMITIVE_ROOT_HPP// #include "primitive_root.hpp"namespace kk2 {template <class FPS, class mint = typename FPS::value_type> void butterfly(FPS &a) {static int g = primitive_root<mint::getmod()>;int n = int(a.size());int h = 0;while ((1U << h) < (unsigned int)(n)) h++;static bool first = true;static mint sum_e2[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]static mint sum_e3[30];static mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1if (first) {first = false;int cnt2 = __builtin_ctz(mint::getmod() - 1);mint e = mint(g).pow((mint::getmod() - 1) >> cnt2), ie = e.inv();for (int i = cnt2; i >= 2; i--) {// e^(2^i) == 1es[i - 2] = e;ies[i - 2] = ie;e *= e;ie *= ie;}mint now = 1;for (int i = 0; i <= cnt2 - 2; i++) {sum_e2[i] = es[i] * now;now *= ies[i];}now = 1;for (int i = 0; i <= cnt2 - 3; i++) {sum_e3[i] = es[i + 1] * now;now *= ies[i + 1];}}int len = 0;while (len < h) {if (h - len == 1) {int p = 1 << (h - len - 1);mint rot = 1;for (int s = 0; s < (1 << len); s++) {int offset = s << (h - len);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p] * rot;a[i + offset] = l + r;a[i + offset + p] = l - r;}if (s + 1 != (1 << len)) rot *= sum_e2[__builtin_ctz(~(unsigned int)(s))];}len++;} else {int p = 1 << (h - len - 2);mint rot = 1, imag = es[0];for (int s = 0; s < (1 << len); s++) {mint rot2 = rot * rot;mint rot3 = rot2 * rot;int offset = s << (h - len);for (int i = 0; i < p; i++) {auto a0 = a[i + offset];auto a1 = a[i + offset + p] * rot;auto a2 = a[i + offset + p * 2] * rot2;auto a3 = a[i + offset + p * 3] * rot3;auto a1na3imag = (a1 - a3) * imag;a[i + offset] = a0 + a2 + a1 + a3;a[i + offset + p] = a0 + a2 - a1 - a3;a[i + offset + p * 2] = a0 - a2 + a1na3imag;a[i + offset + p * 3] = a0 - a2 - a1na3imag;}if (s + 1 != (1 << len)) rot *= sum_e3[__builtin_ctz(~(unsigned int)(s))];}len += 2;}}}template <class FPS, class mint = typename FPS::value_type> void butterfly_inv(FPS &a) {static constexpr int g = primitive_root<mint::getmod()>;int n = int(a.size());int h = 0;while ((1U << h) < (unsigned int)(n)) h++;static bool first = true;static mint sum_ie2[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]static mint sum_ie3[30];static mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1static mint invn[30];if (first) {first = false;int cnt2 = __builtin_ctz(mint::getmod() - 1);mint e = mint(g).pow((mint::getmod() - 1) >> cnt2), ie = e.inv();for (int i = cnt2; i >= 2; i--) {// e^(2^i) == 1es[i - 2] = e;ies[i - 2] = ie;e *= e;ie *= ie;}mint now = 1;for (int i = 0; i <= cnt2 - 2; i++) {sum_ie2[i] = ies[i] * now;now *= es[i];}now = 1;for (int i = 0; i <= cnt2 - 3; i++) {sum_ie3[i] = ies[i + 1] * now;now *= es[i + 1];}invn[0] = 1;invn[1] = mint::getmod() / 2 + 1;for (int i = 2; i < 30; i++) invn[i] = invn[i - 1] * invn[1];}int len = h;while (len) {if (len == 1) {int p = 1 << (h - len);mint irot = 1;for (int s = 0; s < (1 << (len - 1)); s++) {int offset = s << (h - len + 1);for (int i = 0; i < p; i++) {auto l = a[i + offset];auto r = a[i + offset + p];a[i + offset] = l + r;a[i + offset + p] = (l - r) * irot;}if (s + 1 != (1 << (len - 1))) irot *= sum_ie2[__builtin_ctz(~(unsigned int)(s))];}len--;} else {int p = 1 << (h - len);mint irot = 1, iimag = ies[0];for (int s = 0; s < (1 << ((len - 2))); s++) {mint irot2 = irot * irot;mint irot3 = irot2 * irot;int offset = s << (h - len + 2);for (int i = 0; i < p; i++) {auto a0 = a[i + offset];auto a1 = a[i + offset + p];auto a2 = a[i + offset + p * 2];auto a3 = a[i + offset + p * 3];auto a2na3iimag = (a2 - a3) * iimag;a[i + offset] = a0 + a1 + a2 + a3;a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot;a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2;a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3;}if (s + 1 != (1 << (len - 2))) irot *= sum_ie3[__builtin_ctz(~(unsigned int)(s))];}len -= 2;}}for (int i = 0; i < n; i++) a[i] *= invn[h];}template <class FPS, class mint = typename FPS::value_type> void doubling(FPS &a) {int n = a.size();auto b = a;int z = 1;butterfly_inv(b);mint r = 1, zeta = mint(primitive_root<mint::getmod()>).pow((mint::getmod() - 1) / (n << 1));for (int i = 0; i < n; i++) {b[i] *= r;r *= zeta;}butterfly(b);std::copy(b.begin(), b.end(), std::back_inserter(a));}} // namespace kk2#endif // KK2_MATH_MOD_BUTTERFLY_HPP// #include "../math_mod/butterfly.hpp"namespace kk2 {template <class FPS, class mint = typename FPS::value_type> FPS convolution(FPS &a, const FPS &b) {int n = int(a.size()), m = int(b.size());if (!n || !m) return {};if (std::min(n, m) <= 60) {FPS res(n + m - 1);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) { res[i + j] += a[i] * b[j]; }}a = res;return a;}int z = 1;while (z < n + m - 1) z <<= 1;if (a == b) {a.resize(z);butterfly(a);for (int i = 0; i < z; i++) a[i] *= a[i];} else {a.resize(z);butterfly(a);FPS t(b.begin(), b.end());t.resize(z);butterfly(t);for (int i = 0; i < z; i++) a[i] *= t[i];}butterfly_inv(a);a.resize(n + m - 1);return a;}} // namespace kk2#endif // KK2_CONVOLUTION_CONVOLUTION_HPP// #include "../convolution/convolution.hpp"#ifndef KK2_FPS_FPS_HPP#define KK2_FPS_FPS_HPP 1#include <algorithm>#include <cassert>#include <iostream>#include <utility>#include <vector>// #include "../type_traits/type_traits.hpp"namespace kk2 {template <class mint> struct FormalPowerSeries : std::vector<mint> {using std::vector<mint>::vector;using FPS = FormalPowerSeries;template <class OStream, is_ostream_t<OStream> * = nullptr> void display(OStream &os) const {for (int i = 0; i < (int)this->size(); i++) {os << (*this)[i] << " \n"[i == (int)this->size() - 1];}}template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &os) const {for (int i = 0; i < (int)this->size(); i++) {os << (*this)[i] << (i + 1 == (int)this->size() ? "\n" : " ");}}template <class OStream, is_ostream_t<OStream> * = nullptr>friend OStream &operator<<(OStream &os, const FPS &fps_) {for (int i = 0; i < (int)fps_.size(); i++) {os << fps_[i] << (i + 1 == (int)fps_.size() ? "" : " ");}return os;}template <class IStream, is_istream_t<IStream> * = nullptr> FPS &input(IStream &is) {for (int i = 0; i < (int)this->size(); i++) is >> (*this)[i];return *this;}template <class IStream, is_istream_t<IStream> * = nullptr>friend IStream &operator>>(IStream &is, FPS &fps_) {for (auto &x : fps_) is >> x;return is;}FPS &operator+=(const FPS &r) {if (this->size() < r.size()) this->resize(r.size());for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];return *this;}FPS &operator+=(const mint &r) {if (this->empty()) this->resize(1);(*this)[0] += r;return *this;}FPS &operator-=(const FPS &r) {if (this->size() < r.size()) this->resize(r.size());for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];return *this;}FPS &operator-=(const mint &r) {if (this->empty()) this->resize(1);(*this)[0] -= r;return *this;}FPS &operator*=(const mint &r) {for (int i = 0; i < (int)this->size(); i++) { (*this)[i] *= r; }return *this;}FPS &operator/=(const FPS &r) {assert(!r.empty());if (this->size() < r.size()) {this->clear();return *this;}int n = this->size() - r.size() + 1;if ((int)r.size() <= 64) {FPS f(*this), g(r);g.shrink();mint coeff = g.back().inv();for (auto &x : g) x *= coeff;int deg = (int)f.size() - (int)g.size() + 1;int gs = g.size();FPS quo(deg);for (int i = deg - 1; i >= 0; i--) {quo[i] = f[i + gs - 1];for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j];}*this = quo * coeff;this->resize(n, mint(0));return *this;}return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev();}FPS &operator%=(const FPS &r) {*this -= *this / r * r;shrink();return *this;}FPS operator+(const FPS &r) const { return FPS(*this) += r; }FPS operator+(const mint &r) const { return FPS(*this) += r; }FPS operator-(const FPS &r) const { return FPS(*this) -= r; }FPS operator-(const mint &r) const { return FPS(*this) -= r; }FPS operator*(const mint &r) const { return FPS(*this) *= r; }FPS operator/(const FPS &r) const { return FPS(*this) /= r; }FPS operator%(const FPS &r) const { return FPS(*this) %= r; }FPS operator-() const {FPS ret(this->size());for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];return ret;}FPS shrink() {while (this->size() && this->back() == mint(0)) this->pop_back();return *this;}FPS rev() const {FPS ret(*this);std::reverse(ret.begin(), ret.end());return ret;}FPS &inplace_rev() {std::reverse(this->begin(), this->end());return *this;}FPS dot(const FPS &r) const {FPS ret(std::min(this->size(), r.size()));for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i];return ret;}FPS &inplace_dot(const FPS &r) {this->resize(std::min(this->size(), r.size()));for (int i = 0; i < (int)this->size(); i++) (*this)[i] *= r[i];return *this;}FPS pre(int n) const {FPS ret(this->begin(), this->begin() + std::min((int)this->size(), n));if ((int)ret.size() < n) ret.resize(n, mint(0));return ret;}FPS &inplace_pre(int n) {this->resize(n);return *this;}FPS operator>>(int n) const {if (n >= (int)this->size()) return {};FPS ret(this->begin() + n, this->end());return ret;}FPS operator<<(int n) const {FPS ret(*this);ret.insert(ret.begin(), n, mint(0));return ret;}FPS diff() const {const int n = (int)this->size();FPS ret(std::max(0, n - 1));for (int i = 1; i < n; i++) { ret[i - 1] = (*this)[i] * mint(i); }return ret;}FPS &inplace_diff() {if (this->empty()) return *this = FPS();this->erase(this->begin());for (int i = 1; i <= (int)this->size(); i++) (*this)[i - 1] *= mint(i);return *this;}FPS integral() const {const int n = (int)this->size();FPS ret(n + 1);ret[0] = mint(0);if (n > 0) ret[1] = mint(1);auto mod = mint::getmod();for (int i = 2; i <= n; i++) {// p = q * i + r// - q / r = 1 / i (mod p)ret[i] = (-ret[mod % i]) * (mod / i);}for (int i = 0; i < n; i++) { ret[i + 1] *= (*this)[i]; }return ret;}FPS &inplace_int() {static std::vector<mint> inv{0, 1};const int n = this->size();auto mod = mint::getmod();while ((int)inv.size() <= n) {// p = q * i + r// - q / r = 1 / i (mod p)int i = inv.size();inv.push_back((-inv[mod % i]) * (mod / i));}this->insert(this->begin(), mint(0));for (int i = 1; i <= n; i++) (*this)[i] *= inv[i];return *this;}mint eval(mint x) const {mint r = 0, w = 1;for (auto &v : *this) {r += w * v;w *= x;}return r;}FPS log(int deg = -1) const {assert(!this->empty() && (*this)[0] == mint(1));if (deg == -1) deg = this->size();return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}FPS sparse_log(int deg = -1) const {assert(!this->empty() && (*this)[0] == mint(1));if (deg == -1) deg = this->size();std::vector<std::pair<int, mint>> fs;for (int i = 1; i < int(this->size()); i++) {if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);}int mod = mint::getmod();static std::vector<mint> inv{1, 1};while ((int)inv.size() <= deg) {int i = inv.size();inv.push_back(-inv[mod % i] * (mod / i));}FPS g(deg);for (int k = 0; k < deg - 1; k++) {for (auto &[j, fj] : fs) {if (k < j) break;int i = k - j;g[k + 1] -= g[i + 1] * fj * (i + 1);}g[k + 1] *= inv[k + 1];if (k + 1 < int(this->size())) g[k + 1] += (*this)[k + 1];}return g;}template <class T> FPS pow(T k, int deg = -1) const {const int n = this->size();if (deg == -1) deg = n;if (k == 0) {FPS ret(deg);if (deg > 0) ret[0] = mint(1);return ret;}for (int i = 0; i < n; i++) {if ((*this)[i] != mint(0)) {mint rev = mint(1) / (*this)[i];FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);ret *= (*this)[i].pow(k);ret = (ret << (i * k)).pre(deg);if ((int)ret.size() < deg) ret.resize(deg, mint(0));return ret;}if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));}return FPS(deg, mint(0));}template <class T> FPS sparse_pow(T k, int deg = -1) const {if (deg == -1) deg = this->size();if (k == 0) {FPS ret(deg);if (deg > 0) ret[0] = mint(1);return ret;}int zero = 0;while (zero != int(this->size()) && (*this)[zero] == mint(0)) zero++;if (zero == int(this->size()) || __int128_t(zero) * k >= deg) { return FPS(deg, mint(0)); }if (zero != 0) {FPS suf(this->begin() + zero, this->end());auto g = suf.sparse_pow(k, deg - zero * k);FPS ret(zero * k, mint(0));std::copy(std::begin(g), std::end(g), std::back_inserter(ret));return ret;}int mod = mint::getmod();static std::vector<mint> inv{1, 1};while ((int)inv.size() <= deg) {int i = inv.size();inv.push_back(-inv[mod % i] * (mod / i));}std::vector<std::pair<int, mint>> fs;for (int i = 1; i < int(this->size()); i++) {if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);}FPS g(deg);g[0] = (*this)[0].pow(k);mint denom = (*this)[0].inv();k %= mod;for (int a = 1; a < deg; a++) {for (auto &[i, f_i] : fs) {if (a < i) break;g[a] += g[a - i] * f_i * (mint(i) * (k + 1) - a);}g[a] *= denom * inv[a];}return g;}// assume that r is sparse// return this / rFPS sparse_div(const FPS &r, int deg = -1) const {assert(!r.empty() && r[0] != mint(0));if (deg == -1) deg = this->size();mint ir0 = r[0].inv();FPS ret = *this * ir0;ret.resize(deg);std::vector<std::pair<int, mint>> gs;for (int i = 1; i < (int)r.size(); i++) {if (r[i] != mint(0)) gs.emplace_back(i, r[i] * ir0);}for (int i = 0; i < deg; i++) {for (auto &[j, g_j] : gs) {if (i + j >= deg) break;ret[i + j] -= ret[i] * g_j;}}return ret;}FPS sparse_inv(int deg = -1) const {assert(!this->empty() && (*this)[0] != mint(0));if (deg == -1) deg = this->size();std::vector<std::pair<int, mint>> fs;for (int i = 1; i < int(this->size()); i++) {if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);}FPS ret(deg);mint if0 = (*this)[0].inv();if (0 < deg) ret[0] = if0;for (int k = 1; k < deg; k++) {for (auto &[j, fj] : fs) {if (k < j) break;ret[k] += ret[k - j] * fj;}ret[k] *= -if0;}return ret;}FPS sparse_exp(int deg = -1) const {assert(this->empty() || (*this)[0] == mint(0));if (deg == -1) deg = this->size();std::vector<std::pair<int, mint>> fs;for (int i = 1; i < int(this->size()); i++) {if ((*this)[i] != mint(0)) fs.emplace_back(i, (*this)[i]);}int mod = mint::getmod();static std::vector<mint> inv{1, 1};while ((int)inv.size() <= deg) {int i = inv.size();inv.push_back(-inv[mod % i] * (mod / i));}FPS g(deg);if (deg) g[0] = 1;for (int k = 0; k < deg - 1; k++) {for (auto &[ip1, fip1] : fs) {int i = ip1 - 1;if (k < i) break;g[k + 1] += g[k - i] * fip1 * (i + 1);}g[k + 1] *= inv[k + 1];}return g;}FPS &inplace_imos(int n) {inplace_pre(n);for (int i = 0; i < n - 1; i++) { (*this)[i + 1] += (*this)[i]; }return *this;}FPS imos(int n) const {FPS ret(*this);return ret.inplace_imos(n);}FPS &inplace_iimos(int n) {inplace_pre(n);for (int i = 0; i < n - 1; i++) { (*this)[i + 1] -= (*this)[i]; }return *this;}FPS iimos(int n) const {FPS ret(*this);return ret.inplace_iimos(n);}FPS &operator*=(const FPS &r);FPS operator*(const FPS &r) const { return FPS(*this) *= r; }void but();void ibut();void db();static int but_pr();FPS inv(int deg = -1) const;FPS exp(int deg = -1) const;};} // namespace kk2#endif // KK2_FPS_FPS_HPP// #include "fps.hpp"namespace kk2 {template <class mint>FormalPowerSeries<mint> &FormalPowerSeries<mint>::operator*=(const FormalPowerSeries<mint> &r) {if (this->empty() || r.empty()) {this->clear();return *this;}convolution(*this, r);return *this;}template <class mint> void FormalPowerSeries<mint>::but() {butterfly(*this);}template <class mint> void FormalPowerSeries<mint>::ibut() {butterfly_inv(*this);}template <class mint> void FormalPowerSeries<mint>::db() {doubling(*this);}template <class mint> int FormalPowerSeries<mint>::but_pr() {return primitive_root<mint::getmod()>;}template <class mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::inv(int deg) const {assert((*this)[0] != mint(0));if (deg == -1) deg = (int)this->size();FormalPowerSeries<mint> res(deg);res[0] = {mint(1) / (*this)[0]};for (int d = 1; d < deg; d <<= 1) {FormalPowerSeries<mint> f(2 * d), g(2 * d);std::copy(std::begin(*this),std::begin(*this) + std::min((int)this->size(), 2 * d),std::begin(f));std::copy(std::begin(res), std::begin(res) + d, std::begin(g));f.but();g.but();f.inplace_dot(g);f.ibut();std::fill(std::begin(f), std::begin(f) + d, mint(0));f.but();f.inplace_dot(g);f.ibut();for (int j = d; j < std::min(2 * d, deg); j++) res[j] = -f[j];}return res.pre(deg);}template <class mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::exp(int deg) const {assert(this->empty() || (*this)[0] == mint(0));if (deg == -1) deg = (int)this->size();FormalPowerSeries<mint> inv;inv.reserve(deg + 1);inv.push_back(mint(0));inv.push_back(mint(1));FormalPowerSeries<mint> b{1, 1 < (int)this->size() ? (*this)[1] : mint(0)};FormalPowerSeries<mint> c{1}, z1, z2{1, 1};for (int m = 2; m < deg; m <<= 1) {auto y = b;y.resize(m << 1);y.but();z1 = z2;FormalPowerSeries<mint> z(m);z = y.dot(z1);z.ibut();std::fill(std::begin(z), std::begin(z) + (m >> 1), mint(0));z.but();z.inplace_dot(-z1);z.ibut();c.insert(std::end(c), std::begin(z) + (m >> 1), std::end(z));z2 = c;z2.resize(m << 1);z2.but();FormalPowerSeries<mint> x(this->begin(), this->begin() + std::min<int>(this->size(), m));x.resize(m);x.inplace_diff();x.push_back(mint(0));x.but();x.inplace_dot(y);x.ibut();x -= b.diff();x.resize(m << 1);for (int i = 0; i < m - 1; i++) {x[m + i] = x[i];x[i] = mint(0);}x.but();x.inplace_dot(z2);x.ibut();x.pop_back();x.inplace_int();for (int i = m; i < std::min<int>(this->size(), m << 1); i++) x[i] += (*this)[i];std::fill(std::begin(x), std::begin(x) + m, mint(0));x.but();x.inplace_dot(y);x.ibut();b.insert(std::end(b), std::begin(x) + m, std::end(x));}return FormalPowerSeries<mint>(std::begin(b), std::begin(b) + deg);}} // namespace kk2#endif // KK2_FPS_NTT_FRIENDLY_HPP// #include <kk2/fps/ntt_friendly.hpp>#ifndef KK2_FPS_POLY_TAYLOR_SHIFT_HPP#define KK2_FPS_POLY_TAYLOR_SHIFT_HPP 1#include <algorithm>#ifndef KK2_MATH_MOD_COMB_HPP#define KK2_MATH_MOD_COMB_HPP 1#include <algorithm>#include <cassert>#include <vector>// #include "../type_traits/type_traits.hpp"namespace kk2 {template <class mint> struct Comb {static inline std::vector<mint> _fact{1}, _ifact{1}, _inv{1};Comb() = delete;static void extend(int m = -1) {int n = (int)_fact.size();if (m == -1) m = n << 1;if (n > m) return;m = std::min<int>(m, mint::getmod() - 1);_fact.resize(m + 1);_ifact.resize(m + 1);_inv.resize(m + 1);for (int i = n; i <= m; i++) _fact[i] = _fact[i - 1] * i;_ifact[m] = _fact[m].inv();_inv[m] = _ifact[m] * _fact[m - 1];for (int i = m; i > n; i--) {_ifact[i - 1] = _ifact[i] * i;_inv[i - 1] = _ifact[i - 1] * _fact[i - 2];}}static mint fact(int n) {if (n < 0) return 0;if ((int)_fact.size() <= n) extend(n);return _fact[n];}static mint ifact(int n) {if (n < 0) return 0;if ((int)_ifact.size() <= n) extend(n);return _ifact[n];}static mint inv(int n) {if (n < 0) return -inv(-n);if ((int)_inv.size() <= n) extend(n);return _inv[n];}static mint binom(int n, int k) {if (k < 0 || k > n) return 0;return fact(n) * ifact(k) * ifact(n - k);}template <class T> static mint multinomial(const std::vector<T> &r) {static_assert(is_integral<T>::value, "T must be integral");int n = 0;for (auto &x : r) {if (x < 0) return 0;n += x;}mint res = fact(n);for (auto &x : r) res *= ifact(x);return res;}static mint binom_naive(int n, int k) {if (n < 0 || k < 0 || k > n) return 0;mint res = 1;k = std::min(k, n - k);for (int i = 1; i <= k; i++) res *= inv(i) * (n--);return res;}static mint permu(int n, int k) {if (n < 0 || k < 0 || k > n) return 0;return fact(n) * ifact(n - k);}static mint homo(int n, int k) {if (n < 0 || k < 0) return 0;return k == 0 ? 1 : binom(n + k - 1, k);}};} // namespace kk2#endif // KK2_MATH_MOD_COMB_HPP// #include "../math_mod/comb.hpp"namespace kk2 {template <class FPS, class mint = typename FPS::value_type>FPS taylor_shift(const FPS &f_, mint a) {FPS f(f_);int n = f.size();Comb<mint>::extend(n);for (int i = 0; i < n; i++) f[i] *= Comb<mint>::fact(i);f.inplace_rev();FPS g(n, mint(1));for (int i = 1; i < n; i++) g[i] = g[i - 1] * a * Comb<mint>::inv(i);f = (f * g).pre(n).rev();for (int i = 0; i < n; i++) f[i] *= Comb<mint>::ifact(i);return f;}} // namespace kk2#endif // KK2_FPS_POLY_TAYLOR_SHIFT_HPP// #include <kk2/fps/poly_taylor_shift.hpp>#ifndef KK2_MODINT_MONT_HPP#define KK2_MODINT_MONT_HPP 1#include <cassert>#include <cstdint>#include <iostream>#include <type_traits>// #include "../type_traits/type_traits.hpp"namespace kk2 {template <int p> struct LazyMontgomeryModInt {using mint = LazyMontgomeryModInt;using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 get_r() {u32 ret = p;for (int i = 0; i < 4; ++i) ret *= 2 - p * ret;return ret;}static constexpr u32 r = get_r();static constexpr u32 n2 = -u64(p) % p;static_assert(r * p == 1, "invalid, r * p != 1");static_assert(p < (1 << 30), "invalid, p >= 2 ^ 30");static_assert((p & 1) == 1, "invalid, p % 2 == 0");u32 _v;constexpr LazyMontgomeryModInt() : _v(0) {}template <typename T, is_integral_t<T> * = nullptr>constexpr LazyMontgomeryModInt(T b) : _v(reduce(u64(b % p + p) * n2)) {}static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * p) >> 32; }constexpr mint &operator++() { return *this += 1; }constexpr mint &operator--() { return *this -= 1; }constexpr mint operator++(int) {mint ret = *this;*this += 1;return ret;}constexpr mint operator--(int) {mint ret = *this;*this -= 1;return ret;}constexpr mint &operator+=(const mint &b) {if (i32(_v += b._v - 2 * p) < 0) _v += 2 * p;return *this;}constexpr mint &operator-=(const mint &b) {if (i32(_v -= b._v) < 0) _v += 2 * p;return *this;}constexpr mint &operator*=(const mint &b) {_v = reduce(u64(_v) * b._v);return *this;}constexpr mint &operator/=(const mint &b) {*this *= b.inv();return *this;}constexpr mint operator-() const { return mint() - mint(*this); }constexpr bool operator==(const mint &b) const {return (_v >= p ? _v - p : _v) == (b._v >= p ? b._v - p : b._v);}constexpr bool operator!=(const mint &b) const {return (_v >= p ? _v - p : _v) != (b._v >= p ? b._v - p : b._v);}friend constexpr mint operator+(const mint &a, const mint &b) { return mint(a) += b; }friend constexpr mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }friend constexpr mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }friend constexpr mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }template <class T> constexpr mint pow(T n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}constexpr mint inv() const { return pow(p - 2); }template <class OStream, is_ostream_t<OStream> * = nullptr>friend OStream &operator<<(OStream &os, const mint &x) {return os << x.val();}template <class IStream, is_istream_t<IStream> * = nullptr>friend IStream &operator>>(IStream &is, mint &x) {i64 t;is >> t;x = mint(t);return (is);}constexpr u32 val() const {u32 ret = reduce(_v);return ret >= p ? ret - p : ret;}static constexpr u32 getmod() { return p; }};template <int p> using Mont = LazyMontgomeryModInt<p>;using mont998 = Mont<998244353>;using mont107 = Mont<1000000007>;} // namespace kk2#endif // KK2_MODINT_MONT_HPP// #include <kk2/modint/mont.hpp>// #include <kk2/math_mod/comb.hpp>using namespace std;using FPS = kk2::FormalPowerSeries<kk2::mont998>;void solve() {int n;kin >> n;vc<int> a(n);kin >> a;sort(all(a));vc<pair<kk2::mont998, int>> b;for (auto x : a) {if (b.empty() || b.back().first != kk2::mont998(x)) {b.emplace_back(x, 1);} else {b.back().second++;}}vc<FPS> mono(b.size());rep (i, b.size()) mono[i] = FPS{b[i].first.pow(2), 1}.pow(b[i].second, b[i].second + 1);FPS all{1};vc<FPS> c(b.size());rep (i, b.size()) all *= mono[i];rep (i, b.size()) {FPS h = all / mono[i];// by constrainsts, if a[i] != a[j], a[i]^2 != a[j]^2 mod 998244353// so, [x^0]h(x - b[i].first^2) != 0c[i] = kk2::taylor_shift(h, -b[i].first.pow(2)).inv(b[i].second);}kk2::mont998 res = 0;rep (i, b.size()) {rep (j, c[i].size()) {int m = b[i].second - j;res += c[i][j] *kk2::Comb<kk2::mont998>::binom(2 * m - 2, m - 1) *b[i].first.pow(2 * m - 1).inv() *kk2::mont998(2).pow(2 * m - 2).inv();}}kout << res << kendl;}int main() {int t = 1;// kin >> t;rep (t) solve();return 0;}// converted!!// Author: kk2// 2025-01-06 21:51:09