#include // using namespace std; #if __has_include() #include // using namespace atcoder; #endif #define int long long #pragma region header #pragma region alias using lint = long long; using ll = long long; using P = std::pair; template using prique = std::priority_queue,std::greater>; #pragma endregion #pragma region macros #define rep(i, n) for(int i = 0;i<(int)(n);i++) #define REP(i, m, n) for(int i = (m);i<(int)(n);i++) #define drep(i, n) for(int i = (n)-1;i>=0;i--) #define DREP(i, m, n) for(int i = (m)-1;i>=(int)(n);i--) #define all(v) (v).begin(),(v).end() #define reall(v) (v).rbegin(),(v).rend() template bool chmax(T& a,const U b) { if(a < b) { a = b; return true; } return false; } template bool chmin(T& a,const U b) { if(a>b) { a = b; return true; } return false; } std::map prime_div(int n) { std::map mp; if(~n&1) while(~n&1) n>>=1,mp[2]++; for(int i = 3;i<=std::sqrt(n);i+=2) { if(n%i==0) { while(n%i==0) { n/=i; mp[i]++; } } } if(n!=1) mp[n]++; return mp; } bool is_flag(const int &bit, const int &k) { return (bit >> k)&1; } #pragma endregion #pragma region constant constexpr long long inf = 1LL << 61; constexpr int dx[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0}; constexpr int dy[9] = {0, 1, 0, -1, 1, -1, 1, -1, 0}; constexpr long long mod = 1e9+7; constexpr long long MOD = 998244353; #pragma endregion #pragma region inout template std::ostream& operator<<(std::ostream& stream, const std::vector& v) { for(int i = 0; i < (int)(v.size()); i++) { stream << v[i]; if(i != (int)(v.size()) - 1) stream << ' '; } return stream; } template inline void print(const Itr& begin, const Itr& end, bool endline = true, const char* BEGIN = "{", const char* mid = ", ", const char* END = "}") { if(begin == end) return; std::cout << BEGIN << *begin; for(Itr itr = begin+1; itr < end; itr++) std::cout << mid << *itr; std::cout << END; if(endline) std::endl(std::cout); return; } template std::istream& operator>>(std::istream& stream, std::vector& v) { for(T& p:v) stream >> p; return stream; } template inline void input(Itr begin, Itr end) { for(Itr& itr = begin; itr < end; itr++) std::cin >> *itr; return; } template std::ostream& operator<<(std::ostream& stream, const std::pair& pair) { return stream << pair.first << ' ' << pair.second; } template inline void print(const std::pair& pair,const bool endline = true, const char* begin = "(", const char* mid = ", ", const char* end = ")") { std::cout << begin << pair.first << mid << pair.second << end; if(endline) std::endl(std::cout); else std::cout << ' '; return; } template std::istream& operator>>(std::istream& stream, std::pair& pair) { return stream >> pair.first >> pair.second; } template inline void input(std::pair& pair, const bool first = true, const bool second = true) { if(first) std::cin >> pair.first; if(second) std::cin >> pair.second; } #pragma endregion #pragma region DEBUG #ifdef _DEBUG template inline void _debug_view(const T& x) noexcept { std::cout << x; return; } template inline void _debug_view(const std::pair& p) noexcept { std::cout << "("; _debug_view(p.first); std::cout << ", "; _debug_view(p.second); std::cout << ")"; return; } template inline void _debug_view(const std::vector& v) noexcept { std::cout << "{"; for(int i = 0;i inline void _debug_view(const std::map& mp) noexcept { std::cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) { _debug_view(*itr); if(std::next(itr) != mp.end()) std::cout << ", "; } std::cout << "}"; return; } template inline void _debug_view(const std::set& st) noexcept { std::cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) { _debug_view(*itr); if(std::next(itr) != st.end()) std::cout << ", "; } std::cout << "}"; return; } #define overload5(_1,_2,_3,_4,_5,name,...) name #define _debug1(a) {\ do {\ std::cout << #a << ": ";\ _debug_view(a);\ std::endl(std::cout);\ }while(0);\ } #define _debug2(a,b) {\ do {\ std::cout << #a << ": ";\ _debug_view(a);\ std::cout << ", " << #b << ": ";\ _debug_view(b);\ std::endl(std::cout);\ }while(0);\ } #define _debug3(a,b,c) {\ do {\ std::cout << #a << ": ";\ _debug_view(a);\ std::cout << ", " << #b << ": ";\ _debug_view(b);\ std::cout << ", " << #c << ": ";\ _debug_view(c);\ std::endl(std::cout);\ }while(0);\ } #define _debug4(a,b,c,d) {\ do {\ std::cout << #a << ": ";\ _debug_view(a);\ std::cout << ", " << #b << ": ";\ _debug_view(b);\ std::cout << ", " << #c << ": ";\ _debug_view(c);\ std::cout << ", " << #d << ": ";\ _debug_view(d);\ std::endl(std::cout);\ }while(0);\ } #define _debug5(a,b,c,d,e) {\ do {\ std::cout << #a << ": ";\ _debug_view(a);\ std::cout << ", " << #b << ": ";\ _debug_view(b);\ std::cout << ", " << #c << ": ";\ _debug_view(c);\ std::cout << ", " << #d << ": ";\ _debug_view(d);\ std::cout << ", " << #e << ": ";\ _debug_view(e);\ std::endl(std::cout);\ }while(0);\ } #define debug(...) overload5(__VA_ARGS__,_debug5,_debug4,_debug3,_debug2,_debug1,)(__VA_ARGS__) #else #define debug(...) #endif #pragma endregion #pragma endregion template struct FormalPowerSeries : std::vector { using std::vector::vector; using std::vector::operator=; using F = FormalPowerSeries; F operator-() const { F res(*this); for (auto &e : res) e = -e; return res; } F &operator*=(const T &g) { for (auto &e : *this) e *= g; return *this; } F &operator/=(const T &g) { assert(g != T(0)); *this *= g.inv(); return *this; } F &operator+=(const F &g) { int n = (*this).size(), m = g.size(); rep(i, std::min(n, m)) (*this)[i] += g[i]; return *this; } F &operator-=(const F &g) { int n = (*this).size(), m = g.size(); rep(i, std::min(n, m)) (*this)[i] -= g[i]; return *this; } F &operator<<=(const int d) { int n = (*this).size(); (*this).insert((*this).begin(), d, 0); (*this).resize(n); return *this; } F &operator>>=(const int d) { int n = (*this).size(); (*this).erase((*this).begin(), (*this).begin() + std::min(n, d)); (*this).resize(n); return *this; } F inv(int d = -1) const { int n = (*this).size(); assert(n != 0 && (*this)[0] != 0); if (d == -1) d = n; assert(d > 0); F res{(*this)[0].inv()}; while (res.size() < d) { int m = size(res); F f(begin(*this), begin(*this) + std::min(n, 2*m)); F r(res); f.resize(2*m), atcoder::internal::butterfly(f); r.resize(2*m), atcoder::internal::butterfly(r); rep(i, 2*m) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2*m), atcoder::internal::butterfly(f); rep(i, 2*m) f[i] *= r[i]; atcoder::internal::butterfly_inv(f); T iz = T(2*m).inv(); iz *= -iz; rep(i, m) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); } return {res.begin(), res.begin() + d}; } // fast: FMT-friendly modulus only F &operator*=(const F &g) { int n = (*this).size(); *this = convolution(*this, g); (*this).resize(n); return *this; } F &operator/=(const F &g) { int n = (*this).size(); *this = convolution(*this, g.inv(n)); (*this).resize(n); return *this; } // // naive // F &operator*=(const F &g) { // int n = (*this).size(), m = g.size(); // drep(i, n) { // (*this)[i] *= g[0]; // REP(j, 1, std::min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j]; // } // return *this; // } // F &operator/=(const F &g) { // assert(g[0] != T(0)); // T ig0 = g[0].inv(); // int n = (*this).size(), m = g.size(); // rep(i, n) { // REP(j, 1, std::min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j]; // (*this)[i] *= ig0; // } // return *this; // } // sparse F &operator*=(std::vector> g) { int n = (*this).size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; drep(i, n) { (*this)[i] *= c; for (auto &[j, b] : g) { if (j > i) break; (*this)[i] += (*this)[i-j] * b; } } return *this; } F &operator/=(std::vector> g) { int n = (*this).size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); rep(i, n) { for (auto &[j, b] : g) { if (j > i) break; (*this)[i] -= (*this)[i-j] * b; } (*this)[i] *= ic; } return *this; } // multiply and divide (1 + cz^d) void multiply(const int d, const T c) { int n = (*this).size(); if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i]; else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i]; else drep(i, n-d) (*this)[i+d] += (*this)[i] * c; } void divide(const int d, const T c) { int n = (*this).size(); if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i]; else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i]; else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c; } T eval(const T &a) const { T x(1), res(0); for (auto e : *this) res += e * x, x *= a; return res; } F operator*(const T &g) const { return F(*this) *= g; } F operator/(const T &g) const { return F(*this) /= g; } F operator+(const F &g) const { return F(*this) += g; } F operator-(const F &g) const { return F(*this) -= g; } F operator<<(const int d) const { return F(*this) <<= d; } F operator>>(const int d) const { return F(*this) >>= d; } F operator*(const F &g) const { return F(*this) *= g; } F operator/(const F &g) const { return F(*this) /= g; } F operator*(std::vector> g) const { return F(*this) *= g; } F operator/(std::vector> g) const { return F(*this) /= g; } }; using mint = atcoder::modint998244353; using fps = FormalPowerSeries; using sfps = std::vector>; const int MAX = 210; long long fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } signed main() { COMinit(); int n; std::cin >> n; std::vector v(n); std::cin >> v; std::vector a,c; std::map mp; for(const auto &p:v) mp[p]++; for(const auto &p:mp) a.push_back(p.first),c.push_back(p.second); n = a.size(); // debug(a,c); mint final_ans = 0; rep(i, n) { fps f; f.resize(c[i]); f[0] = 1; {//最初の式 fps Y; Y.resize(c[i]); Y[1] = 1; fps sub_f; sub_f.resize(c[i]); sub_f[0] = 1; rep(k, n) { if(i==k) continue; rep(_j, c[k]) { Y[0] = a[k]*a[k]-a[i]*a[i]; sub_f *= Y; } } f*=sub_f; // rep(i, 2) std::cout << f[i].val() << " \n"[i==1]; } mint A = f[0]; fps g = f; g[0] = 0; rep(j, c[i]) f[j] = 0; rep(k, c[i]) {//2番目の式 fps sub_f; sub_f.resize(c[i]); sub_f[0] = 1; rep(_j, k) { sub_f*=g; sub_f/=A; sub_f*=-1; } f+=sub_f; } std::vector p(c[i]); rep(j, c[i]) p[j] = f[j]; // rep(i, 3) std::cout << p[i].val() << " \n"[i==2]; mint ans = 0; rep(j, c[i]) { mint x; x = COM(2*c[i]-2*j,c[i]-j)*(c[i]-j)*p[j]; mint a_i = a[i]; x /= (2*a_i).pow(2*c[i]-2*j) * (2*c[i]-2*j-1); ans+=x; } ans*=2*a[i]; // debug(A.val()); ans/=A; final_ans+=ans; } std::cout << final_ans.val() << std::endl; return 0; }