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;
const int mod = 998244353, B = 1e6, oo = 1e8;
int pow_mod(int x, int n = mod - 2) {
  int y = 1;
  while (n) {
    if (n & 1) {
      y = (long long)y * x % mod;
    }
    x = (long long)x * x % mod;
    n >>= 1;
  }
  return y;
}
struct poly {
  vector<int> p;
  poly() {}
  poly(vector<int> p) : p(p) {}
  poly operator-(const poly &a) const {
    static vector<int> q;
    q = p;
    int n = p.size(), na = a.p.size();
    if (n < na) {
      for (int i = 0; i < n; ++i) {
        q[i] = (q[i] - a.p[i]) % mod;
      }
      for (int i = n; i < na; ++i) {
        q.push_back(-a.p[i]);
      }
    } else {
      for (int i = 0; i < na; ++i) {
        q[i] = (q[i] - a.p[i]) % mod;
      }
    }
    return poly(q);
  }
  poly operator<<(int b) const {
    vector<int> q;
    for (int i = p.size() - 1; ~i; --i) {
      if (!q.size()) {
        q.push_back(p[i]);
      } else {
        q.push_back(0);
        for (int j = q.size() - 2; ~j; --j) {
          q[j + 1] = ((long long)q[j] - (long long)b * q[j + 1]) % mod;
        }
        q[0] = ((long long)p[i] - (long long)b * q[0]) % mod;
      }
    }
    return poly(q);
  }
  void jifen() {
    p.push_back(0);
    for (int i = p.size() - 2; ~i; --i) {
      p[i + 1] = (long long)p[i] * pow_mod(i + 1) % mod;
    }
    p[0] = 0;
    return;
  }
  int y(int x) const {
    int y = 0;
    for (int i = p.size() - 1; ~i; --i) {
      y = ((long long)y * x + p[i]) % mod;
    }
    return y;
  }
};
struct Info {
  int l;
  poly p;
  Info() {}
  Info(int l, poly p) : l(l), p(p) {}
  Info(int l, vector<int> v) : l(l) { p = poly(v); }
  Info(int l, int x) : l(l) { p = poly(vector<int>{x}); }
  Info operator<<(int x) const { return Info(l + x, p << x); }
};
vector<Info> p, q, o;
int n;
int main() {
  scanf("%d", &n);
  p.push_back(Info(0, 1));
  for (int _ = 0; _ < n; ++_) {
    o.clear();
    o.push_back(Info(0, 0));
    for (auto &t : p) {
      o.push_back(t << B);
    }
    q.clear();
    for (int a = 0, b = 0; a < p.size() && b < o.size();) {
      q.push_back(Info(max(p[a].l, o[b].l), p[a].p - o[b].p));
      if (a + 1 == p.size()) {
        ++b;
      } else {
        if (b + 1 == o.size()) {
          ++a;
        } else {
          int nxt = min(p[a + 1].l, o[b + 1].l);
          if (p[a + 1].l == nxt) {
            ++a;
          }
          if (o[b + 1].l == nxt) {
            ++b;
          }
        }
      }
    }
    p.clear();
    for (auto &t : q) {
      t.p.jifen();
      t.p.p[0] = -t.p.y(t.l);
      if (p.size()) {
        t.p.p[0] = (p.back().p.y(t.l) + t.p.p[0]) % mod;
      }
      p.push_back(t);
    }
    double y;
    int x;
    scanf("%lf", &y);
    x = round(y * B);
    while (p.back().l >= x) {
      p.pop_back();
    }
    p.push_back(Info(x, p.back().p.y(x)));
  }
  printf("%d\n", ((long long)p.back().p.y(oo) *
                      pow_mod(B, (long long)n * (mod - 2) % (mod - 1)) % mod +
                  mod) %
                     mod);
  return 0;
}