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 Inv = 616898040, N = 1000000;
int n, C[30 + 5][30 + 5], num[30 + 5], inv[30 + 5], all[30 + 5], sum[30 + 5],
    s[30 + 5], A[30 + 5][30005];
struct Poly {
  int s[33], len;
  Poly() {}
  Poly(int x, int y) {
    memset(s, 0, sizeof(s));
    len = 2;
    s[1] = x;
    s[0] = y;
  }
  Poly operator+(const Poly& y) {
    Poly c;
    memset(c.s, 0, sizeof(c.s));
    c.len = max(len, y.len);
    for (int i = 0; i < c.len; ++i) c.s[i] = (s[i] + y.s[i]) % 998244353;
    return c;
  }
  Poly operator-(const Poly& y) {
    Poly c;
    memset(c.s, 0, sizeof(c.s));
    c.len = max(len, y.len);
    for (int i = 0; i < c.len; ++i)
      c.s[i] = (s[i] - y.s[i] + 998244353) % 998244353;
    return c;
  }
  Poly Trans() {
    Poly c;
    memset(c.s, 0, sizeof(c.s));
    c.len = len;
    for (int i = 0; i < len; ++i)
      for (int j = 0; j <= i; ++j)
        c.s[j] = (c.s[j] + 1LL * s[i] * C[i][j] % 998244353 *
                               ((i - j & 1) ? 998244353 - 1 : 1)) %
                 998244353;
    return c;
  }
  Poly integral() {
    if (!len) return *this;
    Poly c;
    memset(c.s, 0, sizeof(c.s));
    c.len = len + 1;
    for (int i = 0; i < len; ++i)
      c.s[i + 1] = (c.s[i + 1] + 1LL * s[i] * inv[i + 1]) % 998244353;
    return c;
  }
  int Calc(int x) {
    int res = 0;
    for (int i = 0, j = 1; i < len; ++i, j = 1LL * j * x % 998244353)
      res = (res + 1LL * j * s[i]) % 998244353;
    return res;
  }
  void Print() {
    for (int i = len - 1; i >= 0; --i) printf("%dx^%d ", s[i], i);
    puts("");
  }
} a[30 + 5][10005];
inline int pw(int x, int k) {
  int sum = 1;
  for (; k; k >>= 1, x = 1LL * x * x % 998244353)
    if (k & 1) sum = 1LL * sum * x % 998244353;
  return sum;
}
void CalcInter(int x) {
  int tot = 0;
  all[x] = a[x][num[x]].Calc(1LL * A[x][num[x]] * Inv % 998244353);
  for (int i = 1; i <= num[x]; ++i) {
    a[x][i] = a[x][i].integral();
    int valR = a[x][i].Calc(1LL * A[x][i] * Inv % 998244353);
    int valL = a[x][i].Calc(1LL * A[x][i - 1] * Inv % 998244353);
    a[x][i].s[0] = (1LL * a[x][i].s[0] + tot - valL + 998244353) % 998244353;
    tot = (1LL * tot + valR - valL + 998244353) % 998244353;
  }
  sum[x] = tot;
}
Poly Query(int x, int s) {
  if (s <= 0) return a[n + 1][0];
  if (s > A[x][num[x]]) {
    int now = 1LL * A[x][num[x]] * Inv % 998244353;
    return Poly(all[x], (998244353 - 1LL * now * all[x] % 998244353 + sum[x]) %
                            998244353);
  }
  int pos = lower_bound(A[x] + 1, A[x] + num[x] + 1, s) - A[x];
  return a[x][pos];
}
int main() {
  scanf("%d", &n);
  inv[0] = inv[1] = 1;
  double S;
  for (int i = 1; i <= n; ++i)
    scanf("%lf", &S), s[i] = min(int(S * N + 0.5), i * N);
  for (int i = n; --i;) s[i] = min(s[i], s[i + 1]);
  for (int i = 2; i <= n + 2; ++i)
    s[i] = min(s[i], s[i - 1] + N),
    inv[i] = 1LL * (998244353 - 998244353 / i) * inv[998244353 % i] % 998244353;
  for (int i = 0; i <= n + 1; ++i) C[i][0] = 1;
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 998244353;
  num[1] = 1;
  A[1][1] = s[1];
  a[1][1].len = 2;
  a[1][1].s[1] = 1;
  for (int i = 2; i <= n; ++i) {
    A[i][num[i] = 1] = N;
    for (int j = 1; j <= num[i - 1]; ++j)
      A[i][++num[i]] = A[i - 1][j], A[i][++num[i]] = A[i - 1][j] + N;
    sort(A[i] + 1, A[i] + num[i] + 1);
    num[i] = unique(A[i], A[i] + num[i] + 1) - A[i] - 1;
    while (A[i][num[i]] >= s[i]) --num[i];
    A[i][++num[i]] = s[i];
    CalcInter(i - 1);
    for (int j = 1; j <= num[i]; ++j)
      a[i][j] = Query(i - 1, A[i][j]) - Query(i - 1, A[i][j] - N).Trans();
  }
  printf("%d\n", 1LL * a[n][num[n]].Calc(1LL * s[n] * Inv % 998244353));
  return 0;
}