#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}
template <typename T>
inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}
const int N = 935;
const int K = 1000000;
const int mod = 998244353;
int n, m, b[N], c[N], s[N], p[N], len[N], sum[N];
vector<int> a[N];
inline int Qow(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = 1LL * x * x % mod) {
    if (y & 1) {
      r = 1LL * r * x % mod;
    }
  }
  return r;
}
inline vector<int> Solve(const vector<int> &a) {
  vector<int> r(1, 0);
  for (int i = 0; i < a.size(); ++i) {
    r.push_back(1LL * a[i] * Qow(i + 1, mod - 2) % mod);
  }
  return r;
}
inline int F(const vector<int> &a, int x) {
  int r = 0;
  for (int i = a.size() - 1; ~i; --i) {
    r = (1LL * r * x + a[i]) % mod;
  }
  return r;
}
int main() {
  Read(n);
  for (int i = 0; i < n; ++i) {
    double x;
    scanf("%lf", &x);
    s[i] = x * K + 0.5;
    b[i] = s[i] % K;
  }
  b[n] = 0;
  sort(b, b + n + 1), m = unique(b, b + n + 1) - b;
  for (int i = 0; i <= n * m; ++i) {
    p[i] = i / m * K + b[i % m];
  }
  for (int i = 0; i < n; ++i) {
    c[i] = lower_bound(p, p + n * m + 1, s[i]) - p;
  }
  for (int i = 0; i < n * m; ++i) {
    len[i] = 1LL * (p[i + 1] - p[i]) * Qow(K, mod - 2) % mod;
    if (i < min(c[0], m)) {
      a[i] = {0, 1}, sum[i] = len[i];
    } else {
      a[i] = {0}, sum[i] = 0;
    }
  }
  for (int x = 1; x < n; ++x) {
    for (int i = n * m - 1; ~i; --i) {
      if (i >= c[x]) {
        a[i] = {0}, sum[i] = 0;
      } else {
        for (int j = i - 1; j >= i - m && ~j; --j) {
          a[i][0] = (a[i][0] + sum[j]) % mod;
        }
        if (i - m >= 0) {
          while (a[i].size() < a[i - m].size()) {
            a[i].push_back(0);
          }
          for (int j = 0; j < a[i - m].size(); ++j) {
            a[i][j] = (a[i][j] - a[i - m][j] + mod) % mod;
          }
        }
        a[i] = Solve(a[i]);
        sum[i] = F(a[i], len[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n * m; ++i) {
    ans = (ans + sum[i]) % mod;
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}
template <typename T>
inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}
const int N = 935;
const int K = 1000000;
const int mod = 998244353;
int n, m, b[N], c[N], s[N], p[N], len[N], sum[N];
vector<int> a[N];
inline int Qow(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = 1LL * x * x % mod) {
    if (y & 1) {
      r = 1LL * r * x % mod;
    }
  }
  return r;
}
inline vector<int> Solve(const vector<int> &a) {
  vector<int> r(1, 0);
  for (int i = 0; i < a.size(); ++i) {
    r.push_back(1LL * a[i] * Qow(i + 1, mod - 2) % mod);
  }
  return r;
}
inline int F(const vector<int> &a, int x) {
  int r = 0;
  for (int i = a.size() - 1; ~i; --i) {
    r = (1LL * r * x + a[i]) % mod;
  }
  return r;
}
int main() {
  Read(n);
  for (int i = 0; i < n; ++i) {
    double x;
    scanf("%lf", &x);
    s[i] = x * K + 0.5;
    b[i] = s[i] % K;
  }
  b[n] = 0;
  sort(b, b + n + 1), m = unique(b, b + n + 1) - b;
  for (int i = 0; i <= n * m; ++i) {
    p[i] = i / m * K + b[i % m];
  }
  for (int i = 0; i < n; ++i) {
    c[i] = lower_bound(p, p + n * m + 1, s[i]) - p;
  }
  for (int i = 0; i < n * m; ++i) {
    len[i] = 1LL * (p[i + 1] - p[i]) * Qow(K, mod - 2) % mod;
    if (i < min(c[0], m)) {
      a[i] = {0, 1}, sum[i] = len[i];
    } else {
      a[i] = {0}, sum[i] = 0;
    }
  }
  for (int x = 1; x < n; ++x) {
    for (int i = n * m - 1; ~i; --i) {
      if (i >= c[x]) {
        a[i] = {0}, sum[i] = 0;
      } else {
        for (int j = i - 1; j >= i - m && ~j; --j) {
          a[i][0] = (a[i][0] + sum[j]) % mod;
        }
        if (i - m >= 0) {
          while (a[i].size() < a[i - m].size()) {
            a[i].push_back(0);
          }
          for (int j = 0; j < a[i - m].size(); ++j) {
            a[i][j] = (a[i][j] - a[i - m][j] + mod) % mod;
          }
        }
        a[i] = Solve(a[i]);
        sum[i] = F(a[i], len[i]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n * m; ++i) {
    ans = (ans + sum[i]) % mod;
  }
  printf("%d\n", ans);
  return 0;
}

```