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 int64 = long long;
namespace oct {
void sync();
inline void ios() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0), std::cout.tie(0);
}
}  // namespace oct
const int P = 998244353;
inline void add(int &a, int b) {
  a += b;
  if (a >= P) a -= P;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += P;
}
inline int mul(int a, int b) { return (int)((long long)a * b % P); }
inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
inline int inv(int a) { return power(a, P - 2); }
const int N = 77;
int C[N][N];
inline std::vector<int> it(std::vector<int> a) {
  std::vector<int> b = {0};
  for (int i = 0; i < (int)a.size(); i++) b.push_back(mul(a[i], inv(i + 1)));
  return b;
}
void sub(std::vector<int> &a, std::vector<int> b) {
  while (a.size() < b.size()) a.push_back(0);
  for (int i = 0; i < (int)b.size(); i++) sub(a[i], b[i]);
}
std::vector<int> pg(std::vector<int> a, int delta) {
  std::vector<int> b(a.size(), 0);
  for (int i = 0; i < (int)a.size(); i++) {
    for (int j = 0; j <= i; j++) {
      add(b[j], mul(a[i], mul(C[i][j], power(delta, i - j))));
    }
  }
  return b;
}
int gt(std::vector<int> a, int x) {
  int res = 0;
  for (int i = (int)a.size() - 1; i >= 0; i--) {
    res = mul(res, x), add(res, a[i]);
  }
  return res;
}
const int COEFF = 1000000;
int main() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] =
          (j == 0 ? 1 : (i == 0 ? 0 : (C[i - 1][j] + C[i - 1][j - 1]) % P));
    }
  }
  int n;
  std::cin >> n;
  std::vector<int> x(n), fracs;
  for (int i = 0; i < n; i++) {
    double foo;
    std::cin >> foo;
    x[i] = (int)(foo * COEFF + 0.5);
    fracs.push_back(x[i] % COEFF);
  }
  fracs.push_back(0);
  std::sort(fracs.begin(), fracs.end());
  fracs.resize(std::unique(fracs.begin(), fracs.end()) - fracs.begin());
  int c = (int)fracs.size();
  std::vector<int> point(n * c + 1);
  for (int i = 0; i <= n * c; i++) {
    point[i] = mul(i / c * COEFF + fracs[i % c], inv(COEFF));
  }
  std::vector<int> cut(n);
  for (int i = 0; i < n; i++) {
    cut[i] = (int)(find(point.begin(), point.end(), mul(x[i], inv(COEFF))) -
                   point.begin());
  }
  std::vector<std::vector<int> > a(n * c);
  for (int i = 0; i < n * c; i++) a[i] = {i < std::min(c, cut[0]) ? 1 : 0};
  for (int id = 1; id < n; id++) {
    for (int i = 0; i < n * c; i++) a[i] = it(a[i]);
    for (int i = n * c - 1; i >= 0; i--) {
      sub(a[i][0], gt(a[i], point[i]));
      for (int j = i - 1; j >= i - c && j >= 0; j--) {
        add(a[i][0], gt(a[j], point[j + 1]));
        if (j > i - c) {
          sub(a[i][0], gt(a[j], point[j]));
        } else {
          sub(a[i], pg(a[i - c], P - 1));
        }
      }
    }
    for (int i = cut[id]; i < n * c; i++) {
      a[i] = {0};
    }
  }
  int ans = 0;
  for (int i = 0; i < n * c; i++) {
    std::vector<int> b = it(a[i]);
    add(ans, gt(b, point[i + 1]));
    sub(ans, gt(b, point[i]));
  }
  std::cout << ans << '\n';
  return 0;
}