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>
using namespace std;
template <typename T>
bool chmin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}
template <typename T>
bool chmax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  int n = v.size();
  out << "{";
  for (int i = 0; i < n; ++i) {
    if (i) out << ", ";
    out << v[i];
  }
  return out << "}";
}
template <typename A, typename B>
ostream &operator<<(ostream &out, const pair<A, B> &v) {
  return out << "(" << v.first << ", " << v.second << ")";
}
const int P = 998244353;
long long qpow(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) (r *= a) %= P;
    (a *= a) %= P;
    b >>= 1;
  }
  return r;
}
const int e6 = 1000000;
const int ie6 = qpow(e6, P - 2);
const int maxN = 30 + 5;
int n;
vector<int> lim;
vector<long long> fac, ifac;
void prepare(int n) {
  fac.resize(n);
  ifac.resize(n);
  fac[0] = 1;
  for (int i = 1; i < n; ++i) fac[i] = fac[i - 1] * i % P;
  ifac[n - 1] = qpow(fac[n - 1], P - 2);
  for (int i = n - 2; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % P;
}
long long C(int n, int k) {
  if (k < 0 || k > n) return 0;
  assert(n < (int)fac.size());
  return fac[n] * ifac[k] % P * ifac[n - k] % P;
}
void reduce(vector<int> &f) {
  while (f.size() && f.back() == 0) f.pop_back();
}
vector<int> integrate(vector<int> f) {
  int n = f.size();
  vector<int> r(n + 1);
  r[0] = 0;
  for (int i = 1; i < n + 1; ++i)
    r[i] = f[i - 1] * ifac[i] % P * fac[i - 1] % P;
  return r;
}
vector<int> operator+(vector<int> f, vector<int> g) {
  vector<int> p(max(f.size(), g.size()), 0);
  for (size_t i = 0; i < f.size(); ++i) p[i] = f[i];
  for (size_t i = 0; i < g.size(); ++i) p[i] = (p[i] + g[i]) % P;
  reduce(p);
  return p;
}
vector<int> operator-(vector<int> g) {
  vector<int> r = g;
  for (size_t i = 0; i < r.size(); ++i) r[i] = (P - r[i]) % P;
  return r;
}
vector<int> operator-(vector<int> f, vector<int> g) { return f + (-g); }
vector<int> operator*(vector<int> f, vector<int> g) {
  int n = f.size(), m = g.size();
  vector<int> r(n + m - 1, 0);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      r[i + j] = (r[i + j] + (long long)f[i] * g[j]) % P;
  reduce(r);
  return r;
}
int eval(vector<int> f, int x) {
  int r = 0;
  for (int i = (int)f.size() - 1; i >= 0; --i) {
    r = ((long long)r * x + f[i]) % P;
  }
  return r;
}
vector<int> compose(vector<int> f, vector<int> g) {
  vector<int> r;
  for (int i = (int)f.size() - 1; i >= 0; --i) {
    r = r * g + vector<int>(1, f[i]);
  }
  return r;
}
void roll(vector<int> &p, vector<vector<int> > &g, int lim) {
  vector<int> q = p;
  for (auto x : p) q.push_back(x + e6);
  sort(q.begin(), q.end());
  q.erase(unique(q.begin(), q.end()), q.end());
  if (lim <= q.back()) {
    while (q.back() >= lim) q.pop_back();
    q.push_back(lim);
  }
  vector<vector<int> > f;
  for (int i = 0; i + 1 < (int)q.size(); ++i) {
    vector<int> re;
    for (int j = 0; j + 1 < (int)p.size(); ++j) {
      if (q[i] - e6 < p[j + 1] && q[i + 1] > p[j]) {
        assert(q[i + 1] - e6 <= p[j + 1]);
        assert(q[i] >= p[j]);
        auto poly = integrate(g[j]);
        vector<int> now;
        if (q[i] >= p[j + 1])
          now = now + compose(poly, {(int)((long long)p[j + 1] * ie6 % P)});
        else
          now = now + compose(poly, {0, 1});
        if (q[i + 1] - e6 <= p[j])
          now = now - compose(poly, {(int)((long long)p[j] * ie6 % P)});
        else
          now = now - compose(poly, {-1, 1});
        re = re + now;
      }
    }
    f.push_back(re);
  }
  p = q;
  g = f;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    double x;
    cin >> x;
    lim.push_back((int)(x * 1e6 + 0.5));
  }
  for (int i = n - 2; i >= 0; --i) chmin(lim[i], lim[i + 1]);
  {};
  prepare(n + 5);
  vector<int> crit = {0, min(e6, lim[0])};
  vector<vector<int> > polys = {{1}};
  for (int i = 1; i < n; ++i) {
    roll(crit, polys, lim[i]);
    for (auto &p : polys) assert((int)p.size() <= n + 3);
    {};
    {};
  }
  int ans = 0;
  for (int i = 0; i + 1 < (int)crit.size(); ++i) {
    auto f = integrate(polys[i]);
    int seg = eval(f, (long long)crit[i + 1] * ie6 % P) -
              eval(f, (long long)crit[i] * ie6 % P);
    ans = (ans + seg % P) % P;
    assert((int)polys[i].size() <= n + 3);
  }
  cout << ((ans + P) % P) << endl;
  return 0;
}