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;
const int N = 40, M = 1000;
int tmp;
int n, tot, tot2, niyuan[N];
int c[31][31];
int mi(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = 1LL * a * a % mod)
    if (b & 1) s = 1LL * s * a % mod;
  return s;
}
int trans(double s) {
  int X = 1LL * (int)(s * 1000000 + 0.5);
  return X;
}
struct poly {
  int n, L, R;
  int a[N];
  poly() {
    n = 0;
    L = R = 0;
    for (int i = 0; i <= N - 1; ++i) a[i] = 0;
  }
  void setqz(poly s) {
    n = s.n + 1;
    for (int i = 0; i <= s.n; ++i)
      a[i + 1] = 1LL * s.a[i] * niyuan[i + 1] % mod;
    int P = 0;
    a[0] = 0;
    for (int i = n; i >= 0; --i) P = (1LL * P * s.L + a[i]) % mod;
    a[0] = (mod - P) % mod;
  }
  void sethz(poly s) {
    n = s.n + 1;
    for (int i = 0; i <= s.n; ++i)
      a[i + 1] = (mod - 1LL * s.a[i] * niyuan[i + 1] % mod) % mod;
    int P = 0;
    a[0] = 0;
    for (int i = n; i >= 0; --i) P = (1LL * P * s.R + a[i]) % mod;
    a[0] = (mod - P) % mod;
  }
  poly operator+(poly s) {
    poly S;
    S.L = L;
    S.R = R;
    S.n = max(n, s.n);
    for (int i = 0; i <= S.n; ++i) S.a[i] = (a[i] + s.a[i]) % mod;
    return S;
  }
  poly operator-(poly s) {
    poly S;
    S.L = L;
    S.R = R;
    S.n = max(n, s.n);
    for (int i = 0; i <= S.n; ++i) S.a[i] = (mod + a[i] - s.a[i]) % mod;
    return S;
  }
} s[M], t[M * 3];
int z[M * 10], Mi[N];
poly rightmove(poly s) {
  poly r;
  r.L = s.L;
  r.R = s.R;
  r.n = s.n;
  for (int i = 0; i <= s.n; ++i)
    for (int j = 0; j <= i; ++j) {
      int f = ((i - j) & 1) ? (-1) : 1;
      r.a[j] = (1LL * s.a[i] * c[i][j] % mod * (mod + f) % mod * Mi[i - j] +
                r.a[j]) %
               mod;
    }
  return r;
}
int ask(poly s, int x) {
  int P = 0;
  for (int i = s.n; i >= 0; --i) P = (1LL * P * x + s.a[i]) % mod;
  return P;
}
signed main() {
  cin >> n;
  tmp = mi(1000000, mod - 2);
  Mi[0] = 1;
  for (int i = 1; i <= N - 1; ++i) Mi[i] = 1LL * Mi[i - 1] * 1000000 % mod;
  for (int i = 1; i <= N - 1; ++i) niyuan[i] = mi(i, mod - 2);
  ++tot;
  s[tot].L = 0, s[tot].R = 1000000;
  s[tot].n = 0, s[tot].a[0] = 1;
  for (int i = 0; i <= n; ++i) c[i][0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  for (int i = 1; i <= n; ++i) {
    double ed;
    cin >> ed;
    int E = trans(ed);
    for (int j = 1; j <= tot; ++j)
      if (E <= s[j].R) {
        s[j].R = E, tot = j;
        break;
      }
    if (i == n) break;
    tot2 = 0;
    for (int i = 1; i <= tot; ++i) {
      ++tot2;
      t[tot2].L = s[i].L;
      t[tot2].R = min(s[i].R, s[i].L + 1000000);
      t[tot2].setqz(s[i]);
      ++tot2;
      t[tot2].L = t[tot2 - 1].R;
      t[tot2].R = max(s[i].R, s[i].L + 1000000);
      if (s[i].R - s[i].L <= 1000000) {
        t[tot2].n = 0;
        t[tot2].a[0] = ask(t[tot2 - 1], s[i].R);
      } else {
        poly S = t[tot2 - 1] - rightmove(t[tot2 - 1]);
        t[tot2].n = S.n;
        for (int i = 0; i <= t[tot2].n; ++i) t[tot2].a[i] = S.a[i];
      }
      ++tot2;
      t[tot2].L = t[tot2 - 1].R;
      t[tot2].R = s[i].R + 1000000;
      t[tot2].sethz(s[i]);
      t[tot2] = rightmove(t[tot2]);
    }
    int tt = 0, tt2 = 1;
    for (int i = 1; i <= tot2; ++i) z[++tt] = t[i].L, z[++tt] = t[i].R;
    sort(z + 1, z + tt + 1);
    for (int i = 2; i <= tt; ++i)
      if (z[i] - z[i - 1]) z[++tt2] = z[i];
    tot = tt2 - 1;
    s[1].L = z[1];
    for (int i = 2; i <= tt2; ++i) s[i - 1].R = s[i].L = z[i];
    for (int i = 1; i <= tot; ++i) {
      s[i].n = 0;
      for (int j = 0; j <= N - 1; ++j) s[i].a[j] = 0;
    }
    for (int i = 1; i <= tot2; ++i) {
      int L = 0, R = 0;
      for (int j = 1; j <= tot; ++j)
        if (s[j].L - t[i].L == 0) L = j;
      for (int j = 1; j <= tot; ++j)
        if (s[j].R - t[i].R == 0) R = j;
      for (int j = L; j <= R; ++j) s[j] = s[j] + t[i];
    }
  }
  int ans = 0;
  for (int i = 1; i <= tot; ++i) {
    t[i].setqz(s[i]);
    ans += ask(t[i], s[i].R);
    ans %= mod;
  }
  for (int i = 1; i <= n; ++i) ans = 1LL * ans * tmp % mod;
  cout << ans << endl;
}