Problem: At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than 10^6 in total, each one is colored in one of k colors. We can perform the following operation: choose k-1 balloons such that they are of k-1 different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least k-1 different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo 998244353.

Input

The first line contains a single integer k (2 ≤ k ≤ 10^5) —the number of colors.

The second line contains k integers a_1, a_2, …, a_k (0 ≤ a_i) —initial configuration of balloons. a_i is number of balloons of color i. The total number of balloons doesn't exceed 10^6. In other words,

a_1 + a_2 + a_3 + … + a_k ≤ 10^6.

Output

Output number of possible configurations modulo 998244353.

Examples

Input


3
0 1 2


Output


3


Input


4
1 1 1 1


Output


5

Input


5
0 0 1 2 3


Output


1

Input


3
2 2 8


Output


31

Note

In the first example, there are 3 configurations we can get: [0, 1, 2], [2, 0, 1], [1, 2, 0].

In the second example, we can apply the operation not more than once, and possible configurations are: [1, 1, 1, 1], [0, 0, 0, 4], [0, 0, 4, 0], [0, 4, 0, 0], [4, 0, 0, 0]. 

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
template <typename T>
struct modular {
  constexpr modular() : val(0) {}
  constexpr modular(const modular<T>& _m) : val(_m.val) {}
  template <typename U>
  constexpr modular(const U& _r = U()) {
    val = -MOD <= _r && _r < MOD ? _r : _r % MOD;
    if (val < 0) {
      val += MOD;
    }
  }
  const T operator()() { return val; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(val);
  }
  modular<T>& operator+=(const modular<T>& _m) {
    if ((val += _m.val) >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  modular<T>& operator-=(const modular<T>& _m) {
    if ((val -= _m.val) < 0) {
      val += MOD;
    }
    return *this;
  }
  modular<T>& operator*=(const modular<T>& _m) {
    val = modular<T>(static_cast<int64_t>(val) * static_cast<int64_t>(_m.val))
              .val;
    return *this;
  }
  modular<T>& operator/=(const modular<T>& _m) {
    T a = _m.val, b = MOD, u = 0, v = 1;
    while (a != 0) {
      T q = b / a;
      b -= q * a;
      swap(a, b);
      u -= q * v;
      swap(u, v);
    }
    return *this *= u;
  }
  modular<T>& operator=(const modular<T>& _m) {
    val = _m.val;
    return *this;
  }
  template <typename U>
  modular<T>& operator+=(const U& _r) {
    return *this += modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator-=(const U& _r) {
    return *this -= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator*=(const U& _r) {
    return *this *= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator/=(const U& _r) {
    return *this /= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator=(const U& _r) {
    val = modular<T>(_r).val;
    return *this;
  }
  modular<T> operator-() { return modular<T>(-val); }
  template <typename U>
  friend bool operator==(const modular<U>&, const modular<U>&);
  friend std::istream& operator>>(std::istream& os, modular<T>& _m) {
    os >> _m.val;
    _m *= 1;
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, const modular<T>& _m) {
    return os << _m.val;
  }
  template <typename U>
  modular<T> exp(U e) {
    modular<T> res = 1;
    modular<T> b = val;
    if (e < 0) {
      b = 1 / b;
      e *= -1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        res *= b;
      }
      b *= b;
    }
    return res;
  }

 private:
  T val;
};
template <typename T>
inline modular<T> operator+(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T>
inline modular<T> operator-(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T>
inline modular<T> operator*(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T>
inline modular<T> operator/(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T>
inline bool operator==(const modular<T>& _lhs, const modular<T>& _rhs) {
  return _lhs.val == _rhs.val;
}
template <typename T, typename U>
inline bool operator==(const modular<T>& _lhs, const U& _rhs) {
  return _lhs == modular<T>(_rhs);
}
template <typename T, typename U>
inline bool operator==(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) == _rhs;
}
template <typename T>
inline bool operator!=(const modular<T>& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const modular<T>& _lhs, const U& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const U& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
struct Comb {
  int n;
  vector<modular<int> > fac, ifac, inv;
  Comb(int _n = 1) {
    resize(2);
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    n = 1;
    grow(_n);
  }
  void resize(int _s) {
    fac.resize(_s);
    ifac.resize(_s);
    inv.resize(_s);
  }
  bool grow(int _n) {
    if (_n <= n) return false;
    resize(_n + 1);
    for (int i = n + 1; i <= _n; i++) {
      fac[i] = fac[i - 1] * i;
      inv[i] = (-MOD / i) * inv[MOD % i];
      ifac[i] = ifac[i - 1] * inv[i];
    }
    n = _n;
    return true;
  }
  modular<int> c(int N, int K) {
    if (N < K || K < 0) return 0;
    if (N > n) grow(N);
    return fac[N] * ifac[N - K] * ifac[K];
  }
  modular<int> p(int S, int K) { return c(S - 1, K - 1); }
  modular<int> z(int S, int K) { return p(S + K, K); }
};
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  sort(a.begin(), a.end());
  Comb c(n);
  int critical = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] < i) {
      critical = i;
      break;
    }
  }
  modular<int> res;
  if (critical != -1) {
    res = 1;
    for (int i = 1; i < critical; i++) {
      int p = lower_bound(a.begin(), a.end(), i) - a.begin();
      res += c.z(i - p, n);
    }
  } else {
    int S = 0;
    int M = 0;
    vector<int> cnt(n, 0);
    for (auto& x : a) {
      S += x;
      cnt[x %= n]++;
      M += x;
    }
    for (int i = 1; i < n; i++) {
      cnt[i] += cnt[i - 1];
    }
    res = 0;
    for (int i = 0; i < n; i++) {
      int t = S - (M + 1ll * i * n - 1ll * n * (n - cnt[n - i - 1]));
      assert(t % n == 0);
      t /= n;
      res += c.z(t, n);
    }
  }
  cout << res;
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  cout << endl;
  return 0;
}