#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); }
int bt(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
int nxt_C(int x) {
  int c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
long long nxt_C(long long x) {
  long long c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
vector<int> get_bits(int mask) {
  vector<int> bb;
  while (mask) {
    int b = bt(mask);
    bb.push_back(b);
    mask ^= (1 << b);
  }
  reverse(bb.begin(), bb.end());
  return bb;
}
int get_mask(vector<int> v) {
  int mask = 0;
  for (int x : v) {
    mask ^= (1 << x);
  }
  return mask;
}
template <typename T>
void uniq(vector<T>& v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <typename T>
void leftShift(vector<T>& v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T>& v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void sc() {}
template <typename Head, typename... Tail>
void sc(Head& H, Tail&... T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 998244353;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
Mint pwr(Mint a, long long k) {
  Mint ans = 1;
  while (k) {
    if (k & 1) ans = ans * a;
    a = a * a;
    k >>= 1;
  }
  return ans;
}
const int N = 3e5 + 5;
int cnt[N], a[N];
pair<Mint, Mint> operator+(pair<Mint, Mint> a, pair<Mint, Mint> b) {
  return {a.first + b.first, a.second + b.second};
}
pair<Mint, Mint> operator*(pair<Mint, Mint> a, Mint b) {
  return {a.first * b, a.second * b};
}
pair<Mint, Mint> e[N];
Mint val[N];
void solve() {
  int n;
  sc(n);
  int m = 0;
  pair<Mint, Mint> p = {0, 0}, q = {1, 0};
  for (int i = 1; i <= n; i++) {
    sc(a[i]);
    cnt[a[i]]++;
    m += a[i];
  }
  e[0] = q;
  Mint mm = m;
  Mint nn = n;
  for (int i = 0; i <= m - 1; i++) {
    Mint x1 = ((mm * (n - 1) - (mm - i) * (nn - 2)) / (mm - i));
    Mint y1 = (i * (nn - 1) / (mm - i));
    Mint z1 = (mm * (nn - 1) / (mm - i));
    e[i + 1] = q * x1 + p * (-y1) + pair<Mint, Mint>(0, -z1);
    p = e[i], q = e[i + 1];
  }
  Mint e0 = -e[m].second / e[m].first;
  val[0] = e0;
  Mint s = e0 * cnt[0];
  for (int i = 1; i <= m; i++) {
    val[i] = e[i].first * e0 + e[i].second;
    s += cnt[i] * val[i];
  }
  assert(val[m] == 0);
  Mint ans = (nn * s - nn * (nn - 1) * e0) / (nn * nn);
  cout << ans << '\n';
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Slime and his n friends are at a party. Slime has designed a game for his friends to play.

At the beginning of the game, the i-th player has a_i biscuits. At each second, Slime will choose a biscuit randomly uniformly among all a_1 + a_2 + … + a_n biscuits, and the owner of this biscuit will give it to a random uniform player among n-1 players except himself. The game stops when one person will have all the biscuits.

As the host of the party, Slime wants to know the expected value of the time that the game will last, to hold the next activity on time.

For convenience, as the answer can be represented as a rational number p/q for coprime p and q, you need to find the value of (p ⋅ q^{-1})mod 998 244 353. You can prove that qmod 998 244 353 ≠ 0.

Input

The first line contains one integer n\ (2≤ n≤ 100 000): the number of people playing the game.

The second line contains n non-negative integers a_1,a_2,...,a_n\ (1≤ a_1+a_2+...+a_n≤ 300 000), where a_i represents the number of biscuits the i-th person own at the beginning.

Output

Print one integer: the expected value of the time that the game will last, modulo 998 244 353.

Examples

Input


2
1 1


Output


1


Input


2
1 2


Output


3


Input


5
0 0 0 0 35


Output


0


Input


5
8 4 2 0 1


Output


801604029

Note

For the first example, in the first second, the probability that player 1 will give the player 2 a biscuit is 1/2, and the probability that player 2 will give the player 1 a biscuit is 1/2. But anyway, the game will stop after exactly 1 second because only one player will occupy all biscuits after 1 second, so the answer is 1.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); }
int bt(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
int nxt_C(int x) {
  int c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
long long nxt_C(long long x) {
  long long c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
vector<int> get_bits(int mask) {
  vector<int> bb;
  while (mask) {
    int b = bt(mask);
    bb.push_back(b);
    mask ^= (1 << b);
  }
  reverse(bb.begin(), bb.end());
  return bb;
}
int get_mask(vector<int> v) {
  int mask = 0;
  for (int x : v) {
    mask ^= (1 << x);
  }
  return mask;
}
template <typename T>
void uniq(vector<T>& v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <typename T>
void leftShift(vector<T>& v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T>& v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void sc() {}
template <typename Head, typename... Tail>
void sc(Head& H, Tail&... T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 998244353;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
Mint pwr(Mint a, long long k) {
  Mint ans = 1;
  while (k) {
    if (k & 1) ans = ans * a;
    a = a * a;
    k >>= 1;
  }
  return ans;
}
const int N = 3e5 + 5;
int cnt[N], a[N];
pair<Mint, Mint> operator+(pair<Mint, Mint> a, pair<Mint, Mint> b) {
  return {a.first + b.first, a.second + b.second};
}
pair<Mint, Mint> operator*(pair<Mint, Mint> a, Mint b) {
  return {a.first * b, a.second * b};
}
pair<Mint, Mint> e[N];
Mint val[N];
void solve() {
  int n;
  sc(n);
  int m = 0;
  pair<Mint, Mint> p = {0, 0}, q = {1, 0};
  for (int i = 1; i <= n; i++) {
    sc(a[i]);
    cnt[a[i]]++;
    m += a[i];
  }
  e[0] = q;
  Mint mm = m;
  Mint nn = n;
  for (int i = 0; i <= m - 1; i++) {
    Mint x1 = ((mm * (n - 1) - (mm - i) * (nn - 2)) / (mm - i));
    Mint y1 = (i * (nn - 1) / (mm - i));
    Mint z1 = (mm * (nn - 1) / (mm - i));
    e[i + 1] = q * x1 + p * (-y1) + pair<Mint, Mint>(0, -z1);
    p = e[i], q = e[i + 1];
  }
  Mint e0 = -e[m].second / e[m].first;
  val[0] = e0;
  Mint s = e0 * cnt[0];
  for (int i = 1; i <= m; i++) {
    val[i] = e[i].first * e0 + e[i].second;
    s += cnt[i] * val[i];
  }
  assert(val[m] == 0);
  Mint ans = (nn * s - nn * (nn - 1) * e0) / (nn * nn);
  cout << ans << '\n';
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}

```