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 P = 998244353;
int fpow(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = 1LL * k1 * k1 % P)
    if (k2 & 1) k3 = 1LL * k3 * k1 % P;
  return k3;
}
const int N = 35 * 35, B = 1000000, iB = fpow(B, P - 2);
int n, a[N], cut[N], fac[N], inv[N], ifac[N];
vector<int> pos, jia, zhen;
vector<int> A[N];
vector<int> pji(vector<int> a) {
  vector<int> b{0};
  for (int i = 0; i < ((int)(a).size()); ++i)
    b.push_back(1LL * a[i] * fpow(i + 1, P - 2) % P);
  while (((int)(b).size()) > 1 && b.back() == 0) b.pop_back();
  return b;
}
int fun(vector<int> a, int x) {
  int res = 0, bs = 1;
  for (int i = 0; i < ((int)(a).size()); ++i) {
    if (i) bs = 1LL * bs * x % P;
    (res += 1LL * a[i] * bs % P) %= P;
  }
  return res;
}
vector<int> psub(vector<int> a, vector<int> b) {
  a.resize(max(((int)(a).size()), ((int)(b).size())));
  for (int i = 0; i < ((int)(b).size()); ++i) a[i] = (a[i] + P - b[i]) % P;
  return a;
}
int C(int k1, int k2) {
  if (k1 < 0 || k2 < 0 || k1 - k2 < 0) return 0;
  return 1LL * fac[k1] * ifac[k2] % P * ifac[k1 - k2] % P;
}
vector<int> shift(vector<int> a, int k) {
  vector<int> b(((int)(a).size()));
  for (int i = (0); i <= (((int)(a).size()) - 1); ++i) {
    for (int j = (0); j <= (i); ++j) {
      (b[j] += 1LL * a[i] * fpow(k, i - j) % P * C(i, j) % P) %= P;
    }
  }
  return b;
}
int main() {
  fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i < N; ++i)
    fac[i] = 1LL * fac[i - 1] * i % P,
    inv[i] = 1LL * (P - P / i) * inv[P % i] % P,
    ifac[i] = 1LL * ifac[i - 1] * inv[i] % P;
  scanf("%d", &n);
  for (int i = (0); i <= (n - 1); ++i) {
    double k1;
    scanf("%lf", &k1);
    a[i] = (int)(k1 * B + .5);
    pos.push_back(a[i] % B);
  }
  pos.push_back(0);
  sort(pos.begin(), pos.end());
  pos.erase(unique(pos.begin(), pos.end()), pos.end());
  jia.assign(((int)(pos).size()) * n + 1, 0);
  zhen.assign(((int)(pos).size()) * n + 1, 0);
  for (int i = (0); i <= (((int)(pos).size()) * n); ++i)
    jia[i] = i / ((int)(pos).size()) * B + pos[i % ((int)(pos).size())],
    zhen[i] = 1LL * jia[i] * iB % P;
  for (int i = (0); i <= (n - 1); ++i)
    cut[i] = lower_bound(jia.begin(), jia.end(), a[i]) - jia.begin();
  for (int i = (0); i <= (((int)(pos).size()) * n); ++i)
    A[i] = {i < min(((int)(pos).size()), cut[0]) ? 1 : 0};
  for (int _ = (1); _ <= (n - 1); ++_) {
    for (int i = (0); i <= (((int)(pos).size()) * n); ++i) A[i] = pji(A[i]);
    for (int i = (((int)(pos).size()) * n - 1); i >= (0); --i) {
      A[i][0] = (A[i][0] + P - fun(A[i], zhen[i])) % P;
      for (int j = i - 1; j >= i - ((int)(pos).size()) && j >= 0; --j) {
        A[i][0] = (A[i][0] + fun(A[j], zhen[j + 1])) % P;
        if (j > i - ((int)(pos).size())) {
          A[i][0] = (A[i][0] + P - fun(A[j], zhen[j])) % P;
        } else {
          A[i] = psub(A[i], shift(A[j], P - 1));
        }
      }
    }
    for (int i = (cut[_]); i <= (((int)(pos).size()) * n); ++i) A[i] = {0};
  }
  int ans = 0;
  for (int i = (0); i <= (((int)(pos).size()) * n - 1); ++i) {
    ans = ((long long)ans + fun(pji(A[i]), zhen[i + 1]) + P -
           fun(pji(A[i]), zhen[i])) %
          P;
  }
  printf("%d\n", ans);
  return 0;
}