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;
struct mint {
  int x;
  mint(int x = 0) : x(x) {}
};
inline mint operator+(mint a, mint b) {
  return a.x + b.x < MOD ? a.x + b.x : a.x + b.x - MOD;
}
inline mint operator-(mint a) { return MOD - a.x; }
inline mint operator-(mint a, mint b) { return a + -b; }
inline mint operator*(mint a, mint b) { return 1LL * a.x * b.x % MOD; }
inline mint operator<<(mint x, int y) {
  mint r = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) r = r * x;
  return r;
}
inline mint operator~(mint x) { return x << MOD - 2; }
inline mint operator/(mint a, mint b) { return a * ~b; }
inline mint& operator+=(mint& a, mint b) { return a = a + b; }
inline mint& operator-=(mint& a, mint b) { return a = a - b; }
inline mint& operator*=(mint& a, mint b) { return a = a * b; }
inline mint& operator<<=(mint& x, int y) { return x = x << y; }
inline mint& operator/=(mint& a, mint b) { return a = a / b; }
struct pol {
  int n;
  mint x[30 + 5];
  pol() {
    n = 0;
    memset(x, 0, sizeof(x));
  }
};
struct ff {
  int n, p[30 * 30 + 5];
  pol f[30 * 30 + 5];
  ff() {
    n = 0;
    memset(p, 0, sizeof(p));
  };
} F;
mint C[30 + 5][30 + 5];
void tr(pol& x) {
  for (int i = 0; i <= x.n; ++i)
    for (int j = i; ++j <= x.n;)
      x.x[i] += ((j - i) & 1 ? MOD - 1 : 1) * x.x[j] * C[j][i];
}
ff tr(ff x) {
  for (int i = 1; i <= x.n; ++i) x.p[i] += 1e6, tr(x.f[i]);
  return x;
}
pol operator-(pol a, pol b) {
  pol c;
  c.n = max(a.n, b.n);
  for (int i = 0; i <= c.n; ++i) c.x[i] = a.x[i] - b.x[i];
  return c;
}
ff operator-(ff a, ff b) {
  ff c;
  int i = 1, j = 1;
  while (i <= a.n || j <= b.n) {
    int x = i <= a.n ? a.p[i] : 1e9, y = j <= b.n ? b.p[j] : 1e9;
    c.f[c.n++] = a.f[i - 1] - b.f[j - 1];
    c.p[c.n] = min(x, y);
    if (x <= y) ++i;
    if (y <= x) ++j;
  }
  return c;
}
void sm(pol& x) {
  for (int i = ++x.n; i; --i) x.x[i] = x.x[i - 1] / i;
  x.x[0] = 0;
}
mint cal(pol& p, mint x) {
  mint res = 0, z = 1;
  for (int i = 0; i <= p.n; ++i) res += z * p.x[i], z *= x;
  return res;
}
void sm(ff& x, int d) {
  mint s = 0;
  while (x.p[x.n] >= d) x.f[x.n--] = pol();
  x.p[++x.n] = d;
  for (int i = 1; i <= x.n; ++i) {
    sm(x.f[i]);
    x.f[i].x[0] = s -= cal(x.f[i], x.p[i] / mint(1e6));
    if (i < x.n) s = cal(x.f[i], x.p[i + 1] / mint(1e6));
  }
}
int main() {
  int n, i, j;
  double r;
  scanf("%d", &n);
  for (i = 0; i <= n; ++i)
    for (C[i][0] = j = 1; j <= i; ++j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  F.f[1].x[0] = F.n = 1;
  for (i = 1; i <= n; ++i)
    scanf("%lf", &r), sm(F = F - tr(F), int(r * 1e6 + 0.5));
  printf("%d", F.f[F.n].x[0]);
}