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>
const int N = 100, mod = 998244353;
int n, s[N];
double t;
struct z {
  int x;
  z(int x = 0) : x(x) {}
  friend inline z operator*(z a, z b) { return (long long)a.x * b.x % mod; }
  friend inline z operator-(z a, z b) {
    return (a.x -= b.x) < 0 ? a.x + mod : a.x;
  }
  friend inline z operator+(z a, z b) {
    return (a.x += b.x) >= mod ? a.x - mod : a.x;
  }
} inv[N], C[N][N];
inline z fpow(z a, int b) {
  z s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
inline z trans(int x) { return x * fpow(1000000, mod - 2); }
struct poly : std::vector<z> {
  using std::vector<z>::vector;
  inline z take(z x) {
    z s = 0, p = 1;
    for (int i = 0; i < size(); i++) s = s + p * at(i), p = p * x;
    return s;
  }
  inline poly opposite() {
    poly res = *this;
    for (z &x : res) x.x = x.x ? mod - x.x : 0;
    return res;
  }
};
inline poly operator+(poly a, const poly &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) a[i] = a[i] + b[i];
  return a;
}
inline poly operator-(poly a, const poly &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (int i = 0; i < b.size(); i++) a[i] = a[i] - b[i];
  return a;
}
inline poly integral(poly a) {
  a.push_back(0);
  for (int i = (int)a.size() - 1; i >= 1; i--) a[i] = a[i - 1] * inv[i];
  return a.front() = 0, a;
}
struct function : std::vector<std::pair<int, poly>> {
  using std::vector<std::pair<int, poly>>::vector;
  inline void print() {
    for (int i = 0; i < size(); i++) {
      printf("%.3lf : ", at(i).first / 1e6);
      for (z j : at(i).second) printf("%d ", j.x);
      if (i)
        printf("[%d %d]", at(i).second.take(trans(at(i).first)).x,
               at(i - 1).second.take(trans(at(i).first)).x);
      putchar('\n');
    }
  }
  inline function opposite() {
    function res = *this;
    for (auto &it : res) it.second = it.second.opposite();
    return res;
  }
} f[N];
inline function merge(const function &a, const function &b) {
  int i = 0, j = 0;
  poly fa, fb;
  function c;
  while (i < a.size() && j < b.size())
    if (a[i].first == b[j].first) {
      c.push_back({a[i].first, a[i].second + b[j].second});
      fa = a[i++].second;
      fb = b[j++].second;
    } else if (a[i].first < b[j].first) {
      c.push_back({a[i].first, a[i].second + fb});
      fa = a[i++].second;
    } else {
      c.push_back({b[j].first, fa + b[j].second});
      fb = b[j++].second;
    }
  while (i < a.size()) c.push_back({a[i].first, a[i].second + fb}), i++;
  while (j < b.size()) c.push_back({b[j].first, fa + b[j].second}), j++;
  return c;
}
inline function integral(function a) {
  z s = 0;
  for (int i = 0; i + 1 < a.size(); i++) {
    a[i].second = integral(a[i].second);
    s = s - a[i].second.take(trans(a[i].first));
    a[i].second[0] = a[i].second[0] + s;
    s = a[i].second.take(trans(a[i + 1].first));
  }
  a.back().second = integral(a.back().second);
  s = s - a.back().second.take(trans(a.back().first));
  a.back().second[0] = a.back().second[0] + s;
  return a;
}
int main() {
  inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i];
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  }
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lf", &t), s[i] = t * 1000000 + 0.5;
  f[1] = {{0, {0, 1}},
          {std::min(1000000, s[1]), {trans(std::min(1000000, s[1]))}}};
  auto do1 = [&](poly a) {
    poly b(a.size());
    for (int i = 0; i < a.size(); i++)
      for (int j = 0; j <= i; j++)
        if ((i + j) & 1)
          b[j] = b[j] - a[i] * C[i][j];
        else
          b[j] = b[j] + a[i] * C[i][j];
    return b;
  };
  auto do2 = [&](function a) {
    for (auto &it : a) it.first += 1000000, it.second = do1(it.second);
    return a;
  };
  for (int i = 2; i <= n; i++) {
    f[i] = merge(f[i - 1], do2(f[i - 1]).opposite());
    while (f[i].size() && f[i].back().first >= s[i]) f[i].pop_back();
    if (!f[i].size()) return printf("0\n"), 0;
    f[i] = integral(f[i]);
    f[i].push_back({s[i], {f[i].back().second.take(trans(s[i]))}});
  }
  printf("%d\n", f[n].back().second.take(trans(s[n])).x);
}