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, COEFF = 1e6;
inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
inline int mul(int a, int b) { return (int)((long long)a * b % mod); }
inline int power(int a, long long b) {
  int res = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a), b >>= 1;
  }
  return res;
}
inline int inv(int a) { return power(a, mod - 2); }
void sub(vector<int> &a, vector<int> b) {
  while (a.size() < b.size()) {
    a.push_back(0);
  }
  for (int i = 0; i < b.size(); i++) sub(a[i], b[i]);
}
vector<int> integrate(vector<int> a) {
  vector<int> b = {0};
  for (int i = 0; i < a.size(); i++) b.push_back(mul(a[i], inv(i + 1)));
  return b;
}
int eval(vector<int> a, int x) {
  int res = 0;
  for (int i = a.size() - 1; i >= 0; i--) {
    res = mul(res, x);
    add(res, a[i]);
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<int> x(n), uni;
  for (int i = 0; i < n; i++) {
    double in;
    cin >> in;
    x[i] = in * COEFF + 0.5;
    uni.push_back(x[i] % COEFF);
  }
  uni.push_back(0);
  sort(uni.begin(), uni.end());
  uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
  int cnt = uni.size();
  vector<int> point(n * cnt + 1), cut(n), sz(n * cnt);
  for (int i = 0; i <= n * cnt; i++) point[i] = i / cnt * COEFF + uni[i % cnt];
  for (int i = 0; i < n; i++)
    cut[i] = find(point.begin(), point.end(), x[i]) - point.begin();
  for (int i = 0; i < n * cnt; i++)
    sz[i] = mul((point[i + 1] - point[i] + mod) % mod, inv(COEFF));
  vector<vector<int> > a(n * cnt);
  vector<int> sum(n * cnt);
  for (int i = 0; i < n * cnt; i++) {
    a[i] = i < min(cnt, cut[0]) ? vector<int>{0, 1} : vector<int>{0};
    sum[i] = a[i].size() == 2 ? sz[i] : 0;
  }
  for (int id = 1; id < n; id++)
    for (int i = n * cnt - 1; i >= 0; i--) {
      if (i >= cut[id]) {
        a[i] = {0};
        sum[i] = 0;
      } else {
        for (int j = i - 1; j >= max(i - cnt, 0); j--) add(a[i][0], sum[j]);
        if (i - cnt >= 0) sub(a[i], a[i - cnt]);
        a[i] = integrate(a[i]);
        sum[i] = eval(a[i], sz[i]);
      }
    }
  int ans = 0;
  for (int i = 0; i < n * cnt; i++) {
    add(ans, sum[i]);
  }
  cout << ans << endl;
  return 0;
}