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;
long long Rev[35], C[35][35];
long long powmod(long long x, long long y = 998244353 - 2,
                 long long p = 998244353) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % 998244353;
    x = x * x % 998244353;
    y >>= 1;
  }
  return ans;
}
struct Poly {
  long long X[35], L, R;
  Poly() { memset(X, 0, sizeof X); }
  Poly(long long _1) {
    memset(X, 0, sizeof X);
    X[0] = _1;
  }
  long long getval(long long x) {
    long long ans = 0;
    for (long long nw = 1, i = 0; i < 35; i++, nw = nw * x % 998244353)
      ans = (ans + nw * X[i]) % 998244353;
    return ans;
  }
  Poly minus(long long x) {
    Poly Ans;
    for (long long i = 0; i < 35; i++)
      for (long long j = 0, s = 1; j <= i;
           j++, s = s * (998244353 - x) % 998244353)
        Ans.X[i - j] =
            (Ans.X[i - j] + X[i] * C[i][j] % 998244353 * s) % 998244353;
    return Ans;
  }
  Poly intg() {
    Poly Ans;
    for (long long i = 1; i < 35; i++) Ans.X[i] = X[i - 1] * Rev[i] % 998244353;
    Ans.X[0] = 0;
    return Ans;
  }
  Poly operator+(const Poly& A) {
    Poly Ans;
    for (long long i = 0; i < 35; i++) Ans.X[i] = (X[i] + A.X[i]) % 998244353;
    return Ans;
  }
  Poly operator-(const Poly& A) {
    Poly Ans;
    for (long long i = 0; i < 35; i++) Ans.X[i] = (X[i] - A.X[i]) % 998244353;
    return Ans;
  }
  void operator/=(const long long& x) {
    long long tmp = powmod(x);
    for (long long i = 0; i < 35; i++) X[i] = X[i] * tmp % 998244353;
  }
};
long long n, K[33];
vector<Poly> S[33];
int main() {
  for (long long i = 1; i < 35; i++) Rev[i] = powmod(i);
  for (long long i = 0; i < 35; i++)
    for (long long j = 0; j <= i; j++)
      C[i][j] = !j ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % 998244353;
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    double x;
    scanf("%lf", &x);
    K[i] = (long long)(x * 1e6 + 0.5);
  }
  S[1].resize(3);
  S[1][0].L = -1000000;
  S[1][0].R = 0;
  S[1][1].L = 0;
  S[1][1].R = min(K[1], 1000000ll);
  S[1][1].X[0] = powmod(1000000);
  S[1][2].L = min(K[1], 1000000ll);
  S[1][2].R = 1e18;
  for (long long i = 2; i <= n; i++) {
    long long l = 0, r = 1, nw = -1000000;
    S[i].resize(1);
    S[i][0].L = -1000000;
    S[i][0].R = 0;
    K[i] = min(K[i - 1] + 1000000, K[i]);
    while (l < S[i - 1].size()) {
      long long mn = min(S[i - 1][l].R - nw, S[i - 1][r].R - nw - 1000000);
      if (nw + mn + 1000000 >= K[i]) mn = K[i] - nw - 1000000;
      long long x = nw + 1000000;
      Poly X;
      X = X + Poly(S[i - 1][l].intg().getval(S[i - 1][l].R)) -
          S[i - 1][l].intg().minus(1000000);
      X = X + S[i - 1][r].intg().minus(0) -
          Poly(S[i - 1][r].intg().getval(S[i - 1][r].L));
      for (long long j = l + 1; j < r; j++)
        X = X + Poly(S[i - 1][j].intg().getval(S[i - 1][j].R) -
                     S[i - 1][j].intg().getval(S[i - 1][j].L));
      X.L = x;
      X.R = x + mn;
      if (S[i - 1][l].R == mn + x - 1000000) l++;
      if (S[i - 1][r].R == mn + x) r++;
      X /= 1000000;
      S[i].push_back(X);
      if (mn + x == K[i]) break;
      nw = mn + nw;
    }
    Poly X;
    X.L = K[i];
    X.R = 1e18;
    S[i].push_back(X);
  }
  long long ans = 0;
  for (long long i = 1; i + 1 < S[n].size(); i++)
    ans = (ans + S[n][i].intg().getval(S[n][i].R) -
           S[n][i].intg().getval(S[n][i].L)) %
          998244353;
  printf("%lld\n", (ans % 998244353 + 998244353) % 998244353);
  return 0;
}