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;
int n, C[32][32], s[32];
int num[32], inv[32];
int sum[32], all[32];
int F[32][10005];
struct Poly {
  int a[33], len;
  Poly() { memset(a, 0, sizeof(a)); }
  Poly(int x, int y) {
    memset(a, 0, sizeof(a));
    len = 2;
    a[1] = x;
    a[0] = y;
  }
  friend Poly operator+(const Poly &a, const Poly &b) {
    Poly c;
    c.len = max(a.len, b.len);
    for (int i = 0; i < c.len; i++) c.a[i] = (a.a[i] + b.a[i]) % 998244353;
    return c;
  }
  friend Poly operator-(const Poly &a, const Poly &b) {
    Poly c;
    c.len = max(a.len, b.len);
    for (int i = 0; i < c.len; i++)
      c.a[i] = (a.a[i] + 998244353 - b.a[i]) % 998244353;
    return c;
  }
  Poly trans() {
    Poly c;
    c.len = len;
    for (int i = 0; i < len; i++)
      for (int j = 0; j <= i; j++)
        c.a[j] = (c.a[j] + 1ll * a[i] * C[i][j] % 998244353 *
                               ((i - j) & 1 ? 998244353 - 1 : 1)) %
                 998244353;
    return c;
  }
  Poly jifen() {
    if (!len) return *this;
    Poly c;
    c.len = len + 1;
    for (int i = 0; i < len; i++)
      c.a[i + 1] = 1ll * a[i] * inv[i + 1] % 998244353;
    return c;
  }
  int calc(int x) {
    int ans = 0;
    for (int j = len - 1; j >= 0; j--) ans = (1ll * ans * x + a[j]) % 998244353;
    return ans;
  }
} a[32][10005];
void calcinter(int x) {
  int tot = 0;
  all[x] = a[x][num[x]].calc(1ll * F[x][num[x]] * 616898040 % 998244353);
  for (int i = 1; i <= num[x]; i++) {
    a[x][i] = a[x][i].jifen();
    int vr = a[x][i].calc(1ll * F[x][i] * 616898040 % 998244353);
    int vl = a[x][i].calc(1ll * F[x][i - 1] * 616898040 % 998244353);
    a[x][i].a[0] = (1ll * a[x][i].a[0] + tot - vl + 998244353) % 998244353;
    tot = (1ll * tot + vr + 998244353 - vl) % 998244353;
  }
  sum[x] = tot;
}
Poly query(int x, int s) {
  if (s <= 0) return a[n + 1][0];
  if (s > F[x][num[x]]) {
    int now = 1ll * F[x][num[x]] * 616898040 % 998244353;
    return Poly(all[x], (sum[x] + 998244353 - 1ll * now * all[x] % 998244353) %
                            998244353);
  }
  int pos = lower_bound(F[x] + 1, F[x] + num[x] + 1, s) - F[x];
  return a[x][pos];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    double v;
    scanf("%lf", &v);
    s[i] = min((int)(v * 1000000 + 0.5), i * 1000000);
  }
  for (int i = n - 1; i; i--) s[i] = min(s[i], s[i + 1]);
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= n + 2; i++) {
    s[i] = min(s[i], s[i - 1] + 1000000);
    inv[i] = 1ll * (998244353 - 998244353 / i) * inv[998244353 % i] % 998244353;
  }
  for (int i = 0; i <= n + 1; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 998244353;
  }
  num[1] = 1;
  F[1][1] = s[1];
  a[1][1].len = 2;
  a[1][1].a[1] = 1;
  for (int i = 2; i <= n; i++) {
    num[i] = 1;
    F[i][1] = 1000000;
    for (int j = 1; j <= num[i - 1]; j++)
      F[i][++num[i]] = F[i - 1][j], F[i][++num[i]] = F[i - 1][j] + 1000000;
    sort(F[i] + 1, F[i] + num[i] + 1);
    num[i] = unique(F[i], F[i] + num[i] + 1) - F[i] - 1;
    for (; F[i][num[i]] >= s[i]; num[i]--)
      ;
    F[i][++num[i]] = s[i];
    calcinter(i - 1);
    for (int j = 1; j <= num[i]; j++)
      a[i][j] = query(i - 1, F[i][j]) - query(i - 1, F[i][j] - 1000000).trans();
  }
  printf("%d\n", a[n][num[n]].calc(1ll * s[n] * 616898040 % 998244353));
}