Problem: You generate real numbers s1, s2, ..., sn as follows: 

  * s0 = 0; 
  * si = si - 1 + ti, where ti is a real number chosen independently uniformly at random between 0 and 1, inclusive. 



You are given real numbers x1, x2, ..., xn. You are interested in the probability that si ≤ xi is true for all i simultaneously.

It can be shown that this can be represented as <image>, where P and Q are coprime integers, and <image>. Print the value of P·Q - 1 modulo 998244353.

Input

The first line contains integer n (1 ≤ n ≤ 30).

The next n lines contain real numbers x1, x2, ..., xn, given with at most six digits after the decimal point (0 < xi ≤ n).

Output

Print a single integer, the answer to the problem.

Examples

Input

4
1.00
2
3.000000
4.0


Output

1


Input

1
0.50216


Output

342677322


Input

2
0.5
1.0


Output

623902721


Input

6
0.77
1.234567
2.1
1.890
2.9999
3.77


Output

859831967

Note

In the first example, the sought probability is 1 since the sum of i real numbers which don't exceed 1 doesn't exceed i.

In the second example, the probability is x1 itself.

In the third example, the sought probability is 3 / 8.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <typename T>
struct xgcd_s {
  T m, n, gcd;
};
template <typename T>
xgcd_s<T> xgcd(T a, T b) {
  T m[] = {1, 0}, n[] = {0, 1}, q[] = {0, 0};
  for (int i = 0;; i ^= 1) {
    m[i] -= m[i ^ 1] * q[i];
    n[i] -= n[i ^ 1] * q[i];
    if (!b) return xgcd_s<T>{m[i], n[i], a};
    q[i] = a / b;
    a %= b;
    std::swap(a, b);
  }
}
template <unsigned M()>
struct _intmod {
 private:
  struct _p {
    unsigned x;
  };
  _intmod(_p x) { n = x.x; }

 public:
  unsigned n;
  _intmod() { n = 0; }
  _intmod(int x) { n = x < 0 ? M() + x % (int)M() : x % M(); }
  _intmod(unsigned x) { n = x % M(); }
  _intmod(long x) { n = unsigned(x < 0 ? M() + x % (long)M() : x % M()); }
  _intmod(unsigned long x) { n = x % M(); }
  _intmod(long long x) {
    n = unsigned(x < 0 ? M() + x % (long long)M() : x % M());
  }
  _intmod(unsigned long long x) { n = x % M(); }
  _intmod operator+(_intmod b) const { return {n + b.n}; }
  _intmod operator*(_intmod b) const {
    return {_p{unsigned((unsigned long long)n * b.n % M())}};
  }
  _intmod operator-(_intmod b) const {
    return {_p{n >= b.n ? n - b.n : M() + n - b.n}};
  }
  _intmod operator-() const { return {_p{n ? M() - n : 0U}}; }
  _intmod& operator+=(_intmod b) { return (*this = *this + b); }
  _intmod& operator-=(_intmod b) { return (*this = *this - b); }
  _intmod& operator/=(_intmod b) { return (*this = *this / b); }
  _intmod& operator*=(_intmod b) { return (*this = *this * b); }
  static _intmod mulinv(_intmod n) {
    xgcd_s<signed> x = xgcd<signed>(n.n, M());
    assert(x.gcd == 1);
    return x.m;
  }
  _intmod operator/(_intmod b) const { return *this * mulinv(b); }
  bool operator==(_intmod b) const { return n == b.n; }
  bool operator!=(_intmod b) const { return n != b.n; }
  explicit operator int() const { return n; }
};
template <unsigned M()>
std::ostream& operator<<(std::ostream& o, _intmod<M> n) {
  return o << n.n;
}
template <unsigned M()>
std::istream& operator>>(std::istream& i, _intmod<M>& n) {
  long long x;
  i >> x;
  n = x;
  return i;
}
template <unsigned M>
unsigned intmod_unsignedconst() {
  static_assert(M > 0 && M < (1U << 31), "modulus bad");
  return M;
}
template <unsigned* M>
unsigned intmod_unsignedptr() {
  return *M;
}
template <unsigned M>
using intmod = _intmod<intmod_unsignedconst<M> >;
template <unsigned* M>
using intmodv = _intmod<intmod_unsignedptr<M> >;
static_assert(std::is_trivially_copyable<intmod<3> >::value, "");
template <typename I = int, typename V = bool>
struct segmap {
  std::map<I, V> tr;
  struct seg {
    I l, r;
    V v;
  };
  struct iter {
    I a, b;
    typename std::map<I, V>::const_iterator i;
    seg operator*() {
      auto i2 = i;
      ++i2;
      return {std::max(a, i->first), std::min(b, i2->first), i->second};
    }
    iter& operator--() {
      --i;
      return *this;
    }
    iter& operator++() {
      ++i;
      return *this;
    }
    bool operator!=(const iter& o) { return i != o.i; }
  };
  struct range_s {
    std::map<I, V>& tr;
    I a, b;
    iter begin() { return {a, b, --tr.upper_bound(a)}; }
    iter end() { return {a, b, tr.lower_bound(b)}; }
  };
  range_s range(I a, I b) { return range_s{tr, a, b}; }
  iter begin() {
    auto beg = tr.begin();
    return {beg->first, tr.rbegin()->first, beg};
  }
  iter end() {
    auto e = --tr.end();
    return {tr.begin()->first, e->first, e};
  }
  void init(I min, I max, V v = {}) {
    tr.clear();
    tr.insert({min, v});
    tr.insert({max, v});
  }
  segmap(I min, I max, V v = {}) { init(min, max, v); }
  segmap() {}
  segmap(const segmap& o) : tr(o.tr) {}
  const V& operator[](I i) {
    auto it = tr.upper_bound(i);
    --it;
    return it->second;
  }
  seg get(I x) {
    auto it = tr.upper_bound(x);
    I r = it->first;
    --it;
    return {it->first, r, it->second};
  }
  void set(I a, I b, V v) {
    if (!(b > a)) return;
    I l, r;
    V lv, rv;
    auto il = tr.lower_bound(a), ir = tr.lower_bound(b);
    if (il == tr.begin()) {
      l = a;
    } else {
      --il;
      l = il->first;
      lv = il->second;
    }
    r = ir->first;
    if (r == b) {
      rv = ir->second;
    } else {
      auto rp = ir;
      --rp;
      rv = rp->second;
    }
    if (l != a) ++il;
    if (r == b && rv == v) {
      ++ir;
      if (ir == tr.end()) --ir;
    }
    tr.erase(il, ir);
    if (!(l != a && lv == v)) tr.insert({a, v});
    if (r != b && !(rv == v)) tr.insert({b, rv});
  }
  template <typename Func>
  void transform(I a, I b, Func f) {
    while (a < b) {
      seg s = get(a);
      set(a, std::min(b, s.r), f(s.v));
      a = s.r;
    }
  }
  void swap(segmap& o) { std::swap(tr, o.tr); }
};
using namespace std;
using I = intmod<998244353>;
using poly = array<I, 31>;
I fact[31]{1};
poly add(const poly& a, const poly& b) {
  poly o;
  for (int i = 31; i--;) o[i] = a[i] + b[i];
  return o;
}
poly integrate(const poly& p) {
  poly o;
  o[0] = 0;
  for (int i = 1; i < 31; i++) o[i] = p[i - 1] / i;
  return o;
}
I eval(const poly& p, I x) {
  x /= 1000000;
  I o = 0;
  for (auto i = p.rbegin(); i != p.rend(); ++i) o = o * x + *i;
  return o;
}
poly translate(const poly& p) {
  poly o{};
  for (int i = 0; i < 31; i++)
    for (int j = 31; --j >= i;)
      o[i] +=
          fact[j] / (fact[i] * fact[j - i]) * (((i ^ j) & 1) ? -1 : 1) * p[j];
  return o;
}
int main(int argc, char** argv) {
  if (argc == 2) freopen(argv[1], "r", stdin);
  ios_base::sync_with_stdio(0);
  for (int i = 1; i < 31; i++) fact[i] = fact[i - 1] * i;
  int n;
  cin >> n;
  vector<int> x(n);
  segmap<int, poly> s(0, 1000000, {1});
  for (int i = 1;;) {
    double d;
    cin >> d;
    int x = d * 1000000 + 0.5;
    s.set(x, i * 1000000, {});
    if (++i > n) break;
    decltype(s) s2(0, i * 1000000, {});
    for (auto seg : s) {
      poly in = integrate(seg.v);
      poly tr = translate(in);
      for (I& x : tr) x = -x;
      I inl = eval(in, seg.l);
      I inr = eval(in, seg.r);
      if (seg.r - seg.l > 1000000) {
        poly mid = add(in, tr);
        s2.transform(seg.l + 1000000, seg.r,
                     [&mid](poly& p) { return add(p, mid); });
      } else {
        I c = inr - inl;
        s2.transform(seg.r, seg.l + 1000000, [c](poly p) {
          p[0] += c;
          return p;
        });
      }
      in[0] = -inl;
      s2.transform(seg.l, min(seg.r, seg.l + 1000000),
                   [&in](poly& p) { return add(p, in); });
      tr[0] += inr;
      s2.transform(max(seg.l + 1000000, seg.r), seg.r + 1000000,
                   [&tr](poly& p) { return add(p, tr); });
    }
    s = move(s2);
  }
  I an = 0;
  for (auto seg : s) {
    poly in = integrate(seg.v);
    an += eval(in, seg.r) - eval(in, seg.l);
  }
  cout << an;
  return 0;
}