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 long long M = 998244353, mgc = 1000000;
long long inv(long long x, long long m = M) {
  return x <= 1 ? x : ((1 - inv(m % x, x) * m) / x + m) % m;
}
struct poly {
  vector<long long> v;
  inline long long& operator[](int i) {
    if (v.size() <= i) v.resize(i + 1);
    return v[i];
  }
  inline long long operator()(long long x) {
    long long res = 0;
    for (int i = v.size() - 1; i >= 0; --i) res = (res * x + v[i]) % M;
    return res;
  }
  inline void integrate() {
    if (v.empty() || v.back()) v.push_back(0);
    for (int i = v.size() - 1; i; --i) v[i] = v[i - 1] * inv(i) % M;
    v[0] = 0;
  }
} dp1[930];
int n, fc, cut[30];
long long x[30], pt[931], dist[930], dp2[930];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vector<int> f = {0};
  for (int i = 0; i < n; ++i) {
    double d;
    cin >> d;
    x[i] = (long long)(d * mgc + 0.5);
    f.push_back(x[i] % mgc);
  }
  sort(f.begin(), f.end());
  f.resize(unique(f.begin(), f.end()) - f.begin());
  fc = f.size();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < fc; ++j) pt[i * fc + j] = (i + f[j] * inv(mgc)) % M;
  pt[n * fc] = n;
  for (int i = 0; i < n; ++i)
    cut[i] = find(pt, pt + n * fc + 1, (x[i] * inv(mgc)) % M) - pt;
  for (int i = 0; i < n * fc; ++i) dist[i] = (pt[i + 1] - pt[i] + M) % M;
  for (int i = 0; i < n * fc; ++i) {
    if (i < min(fc, cut[0])) {
      dp1[i][1] = 1;
      dp2[i] = dist[i];
    }
  }
  for (int k = 1; k < n; ++k) {
    for (int i = n * fc - 1; i >= 0; --i) {
      if (i >= cut[k]) {
        dp1[i].v.clear();
        dp2[i] = 0;
      } else {
        for (int j = i - 1; j >= max(i - fc, 0); --j) dp1[i][0] += dp2[j];
        dp1[i][0] %= M;
        if (i - fc >= 0)
          for (int j = 0; j < dp1[i - fc].v.size(); ++j)
            dp1[i][j] = (dp1[i][j] - dp1[i - fc][j] + M) % M;
        dp1[i].integrate();
        dp2[i] = dp1[i](dist[i]);
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < n * fc; ++i) ans += dp2[i];
  cout << ans % M;
}