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 long long p = 998244353;
long long n, inve[35], q[35];
vector<long long> v, w;
long long dp[35][35 * 35][35];
long long ing[35 * 35];
long long m;
long long t[35];
long long exp(long long x, long long k) {
  if (k == 0) return 1;
  if (k % 2 == 1) return x * exp(x, k - 1) % p;
  long long y = exp(x, k / 2);
  return y * y % p;
}
long long inv(long long x) { return exp(x, p - 2); }
long long integral(long long k, long long x, long long l, long long r) {
  long long tot = 0;
  long long pl = 1, pr = 1;
  for (int i = 0; i <= 32; ++i) {
    pl = l * pl % p;
    pr = r * pr % p;
    tot = (tot + inve[i + 1] * (pr + p - pl) % p * dp[k][x][i]) % p;
  }
  return tot;
}
int main() {
  cin >> n;
  m = n * n + n;
  for (int i = 1; i < 35; ++i) inve[i] = inv(i);
  for (int i = 0; i <= n; ++i) v.push_back(1000000 * i);
  for (int i = 0; i < n; ++i) {
    double x;
    cin >> x;
    long long y = (long long)(1000000 * x + 0.5);
    q[i] = y;
    for (int j = 0; j < n; ++j) {
      v.push_back((j * 1000000 + y) % (n * 1000000));
    }
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); ++i) w.push_back(v[i] * inv(1000000) % p);
  for (int i = 1; i <= n; ++i) {
    if (i == 1) {
      for (int j = 0; j < m; ++j)
        if (v[j + 1] <= q[i - 1] && v[j + 1] <= 1000000) {
          dp[1][j][0] = 1;
        }
      continue;
    }
    for (int j = 0; j < m; ++j) ing[j] = integral(i - 1, j, w[j], w[j + 1]);
    for (int j = 0; j < m; ++j) {
      if (v[j] >= q[i - 1]) break;
      for (int k = j - 1; k >= 0; --k) {
        if (v[k] <= v[j] - 1000000) {
          assert(v[k + 1] >= v[j] - 1000000);
          memset(t, 0, sizeof(t));
          for (int r = 31; r >= 0; --r) {
            for (int u = 31; u >= 0; --u) {
              t[u + 1] = (p + t[u] - t[u + 1]) % p;
            }
            t[0] = (p - t[0]) % p;
            t[0] = (t[0] + inve[r + 1] * dp[i - 1][k][r]) % p;
          }
          for (int u = 32; u >= 0; --u) {
            t[u + 1] = (p + t[u] - t[u + 1]) % p;
          }
          t[0] = (p - t[0]) % p;
          for (int r = 0; r <= 32; ++r)
            dp[i][j][r] = (dp[i][j][r] + p - t[r]) % p;
          dp[i][j][0] = (dp[i][j][0] + integral(i - 1, k, 0, w[k + 1])) % p;
          break;
        }
        dp[i][j][0] = (dp[i][j][0] + ing[k]) % p;
      }
      dp[i][j][0] = (dp[i][j][0] + p - integral(i - 1, j, 0, w[j])) % p;
      for (int k = 1; k <= 32; ++k)
        dp[i][j][k] = (dp[i][j][k] + inve[k] * dp[i - 1][j][k - 1]) % p;
    }
  }
  long long ans = 0;
  for (int i = 0; i < m; ++i) ans = (ans + integral(n, i, w[i], w[i + 1])) % p;
  cout << ans << endl;
}