#include <bits/stdc++.h>
using namespace std;
using vll = vector<long long>;
inline long long getmod(long long n, long long m) { return (n % m + m) % m; }
inline long long getmodinverse(long long a, long long mod) {
  long long b = mod, u = 1, v = 0, t;
  while (b) {
    t = a / b;
    swap(a -= b * t, b);
    swap(u -= v * t, v);
  }
  return getmod(u, mod);
}
template <long long PRIME>
struct zpz {
  long long r;
  zpz() : r(0) {}
  zpz(long long n) : r(n) { assert(0 <= n && n < PRIME); }
  friend zpz operator*(const zpz& x, const zpz& y) {
    return (x.r * y.r) % PRIME;
  }
  friend zpz operator-(const zpz& x, const zpz& y) {
    return (x.r - y.r + PRIME) % PRIME;
  }
  friend zpz operator+(const zpz& x, const zpz& y) {
    return (x.r + y.r) % PRIME;
  }
  friend zpz operator/(const zpz& x, const zpz& y) {
    return (x.r * getmodinverse(y.r, PRIME)) % PRIME;
  }
  zpz operator-() const { return zpz((PRIME - r) % PRIME); }
};
template <typename T>
struct vec3 {
  T a, b, c;
  vec3() : a(0), b(0), c(0) {}
  vec3(T x, T y, T z) : a(x), b(y), c(z) {}
  friend vec3 operator-(const vec3& x, const vec3& y) {
    return vec3(x.a - y.a, x.b - y.b, x.c - y.c);
  }
  friend vec3 operator+(const vec3& x, const vec3& y) {
    return vec3(x.a + y.a, x.b + y.b, x.c + y.c);
  }
  friend vec3 operator*(const vec3& x, const T& f) {
    return vec3(x.a * f, x.b * f, x.c * f);
  }
  friend vec3 operator*(const T& f, const vec3& x) {
    return vec3(x.a * f, x.b * f, x.c * f);
  }
  vec3 operator-() const { return vec3(-a, -b, -c); }
  vec3& operator+=(const vec3& rhs) {
    a = a + rhs.a;
    b = b + rhs.b;
    c = c + rhs.c;
    return *this;
  }
  vec3& operator-=(const vec3& rhs) {
    a = a - rhs.a;
    b = b - rhs.b;
    c = c - rhs.c;
    return *this;
  }
};
static const long long PRIME = 998244353;
static const long long N = 1e5 + 10;
static const long long M = 3e5 + 10;
using frac = zpz<PRIME>;
using frac3 = vec3<frac>;
long long n, m = 0;
vll biscuits(N);
vector<frac3> seq(M);
inline void getinput() {
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> biscuits[i];
    m += biscuits[i];
  }
}
int main(int argc, char const* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  getinput();
  seq[0] = vec3<frac>(1, 0, 0);
  seq[1] = vec3<frac>(0, 1, 0);
  vec3<frac> unit(0, 0, 1);
  for (long long a = 1; a <= m - 1; a++) {
    long long inv = getmodinverse(getmod(m - a, PRIME), PRIME);
    long long num1 = getmod(m + a * n - 2 * a, PRIME);
    long long num2 = getmod(-a * (n - 1), PRIME);
    frac c1((num1 * inv) % PRIME);
    frac c2((num2 * inv) % PRIME);
    seq[a + 1] = c1 * seq[a] + c2 * (seq[a - 1] + unit);
  }
  frac3 add;
  for (int i = 0; i < n; i++) {
    add += seq[biscuits[i]];
  }
  vec3<frac> sub = (n - 1) * seq[0] + seq[m];
  vec3<frac> res = add - sub;
  cout << res.c.r << endl;
  return 0;
}

### Prompt

Generate a CPP solution 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;
using vll = vector<long long>;
inline long long getmod(long long n, long long m) { return (n % m + m) % m; }
inline long long getmodinverse(long long a, long long mod) {
  long long b = mod, u = 1, v = 0, t;
  while (b) {
    t = a / b;
    swap(a -= b * t, b);
    swap(u -= v * t, v);
  }
  return getmod(u, mod);
}
template <long long PRIME>
struct zpz {
  long long r;
  zpz() : r(0) {}
  zpz(long long n) : r(n) { assert(0 <= n && n < PRIME); }
  friend zpz operator*(const zpz& x, const zpz& y) {
    return (x.r * y.r) % PRIME;
  }
  friend zpz operator-(const zpz& x, const zpz& y) {
    return (x.r - y.r + PRIME) % PRIME;
  }
  friend zpz operator+(const zpz& x, const zpz& y) {
    return (x.r + y.r) % PRIME;
  }
  friend zpz operator/(const zpz& x, const zpz& y) {
    return (x.r * getmodinverse(y.r, PRIME)) % PRIME;
  }
  zpz operator-() const { return zpz((PRIME - r) % PRIME); }
};
template <typename T>
struct vec3 {
  T a, b, c;
  vec3() : a(0), b(0), c(0) {}
  vec3(T x, T y, T z) : a(x), b(y), c(z) {}
  friend vec3 operator-(const vec3& x, const vec3& y) {
    return vec3(x.a - y.a, x.b - y.b, x.c - y.c);
  }
  friend vec3 operator+(const vec3& x, const vec3& y) {
    return vec3(x.a + y.a, x.b + y.b, x.c + y.c);
  }
  friend vec3 operator*(const vec3& x, const T& f) {
    return vec3(x.a * f, x.b * f, x.c * f);
  }
  friend vec3 operator*(const T& f, const vec3& x) {
    return vec3(x.a * f, x.b * f, x.c * f);
  }
  vec3 operator-() const { return vec3(-a, -b, -c); }
  vec3& operator+=(const vec3& rhs) {
    a = a + rhs.a;
    b = b + rhs.b;
    c = c + rhs.c;
    return *this;
  }
  vec3& operator-=(const vec3& rhs) {
    a = a - rhs.a;
    b = b - rhs.b;
    c = c - rhs.c;
    return *this;
  }
};
static const long long PRIME = 998244353;
static const long long N = 1e5 + 10;
static const long long M = 3e5 + 10;
using frac = zpz<PRIME>;
using frac3 = vec3<frac>;
long long n, m = 0;
vll biscuits(N);
vector<frac3> seq(M);
inline void getinput() {
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> biscuits[i];
    m += biscuits[i];
  }
}
int main(int argc, char const* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  getinput();
  seq[0] = vec3<frac>(1, 0, 0);
  seq[1] = vec3<frac>(0, 1, 0);
  vec3<frac> unit(0, 0, 1);
  for (long long a = 1; a <= m - 1; a++) {
    long long inv = getmodinverse(getmod(m - a, PRIME), PRIME);
    long long num1 = getmod(m + a * n - 2 * a, PRIME);
    long long num2 = getmod(-a * (n - 1), PRIME);
    frac c1((num1 * inv) % PRIME);
    frac c2((num2 * inv) % PRIME);
    seq[a + 1] = c1 * seq[a] + c2 * (seq[a - 1] + unit);
  }
  frac3 add;
  for (int i = 0; i < n; i++) {
    add += seq[biscuits[i]];
  }
  vec3<frac> sub = (n - 1) * seq[0] + seq[m];
  vec3<frac> res = add - sub;
  cout << res.c.r << endl;
  return 0;
}

```