#include <bits/stdc++.h>
using namespace std;
const long long PW = 1000000;
long long inv;
long long quickpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * quickpow(1ll * x * x % 998244353, k >> 1) *
                      (k & 1 ? x : 1) % 998244353;
}
int C[101][101];
struct func {
  vector<int> v;
  int len;
  func() {}
  func(int len, vector<int> v) : len(len), v(v) {}
  long long cal(int x) {
    int ret = 0, base = 1;
    for (int i = (0); i < (int)(v.size()); ++i)
      ret = (ret + 1ll * v[i] * base) % 998244353,
      base = 1ll * base * x % 998244353;
    return ret;
  }
  func itg(long long coef) {
    func ret;
    ret.len = len;
    ret.v.push_back(0);
    for (int i = (0); i < (int)(v.size()); ++i)
      ret.v.push_back(1ll * v[i] * quickpow(i + 1, 998244353 - 2) % 998244353 *
                      inv % 998244353);
    ret.v[0] = (998244353 - ret.cal(len) + coef) % 998244353;
    return ret;
  }
  func operator-(const func &t) const {
    func ret;
    ret.len = max(len, t.len);
    ret.v.resize(max(v.size(), t.v.size()));
    for (int i = (0); i < (int)(ret.v.size()); ++i) {
      int x = 0;
      if (i < v.size()) x += v[i];
      if (i < t.v.size()) x -= t.v[i];
      ret.v[i] = (x + 998244353) % 998244353;
    }
    return ret;
  }
  func operator>>(int x) {
    func ret;
    int pw[100];
    pw[0] = 1;
    for (int j = (1); j < (int)(v.size() + 1); ++j)
      pw[j] = 1ll * pw[j - 1] * (998244353 - x % 998244353) % 998244353;
    ret.len = len + x;
    ret.v.resize(v.size());
    for (int i = (0); i < (int)(v.size()); ++i) {
      if (v[i] == 0) continue;
      for (int j = (0); j < (int)(i + 1); ++j)
        ret.v[j] = (ret.v[j] + 1ll * C[i][j] * pw[i - j] % 998244353 * v[i]) %
                   998244353;
    }
    return ret;
  }
};
vector<func> v, nv, tv;
long long lm[33];
int main() {
  for (int i = (0); i < (int)(101); ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = (1); j < (int)(i); ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 998244353;
  }
  inv = quickpow(PW, 998244353 - 2);
  vector<int> buf;
  buf.clear();
  buf.push_back(1);
  v.push_back(func(0, buf));
  int n;
  cin >> n;
  for (int i = (0); i < (int)(n); ++i) {
    double x;
    cin >> x;
    lm[i] = int(x * PW + 0.5);
  }
  for (int i = (int)(n - 1) - 1; i >= 0; --i)
    lm[i] = (lm[i] < lm[i + 1] ? lm[i] : lm[i + 1]);
  for (int i = (0); i < (int)(n); ++i) {
    int lim = lm[i];
    for (int j = (0); j < (int)(v.size()); ++j) {
      if (j > 0)
        v[j] = v[j].itg(v[j - 1].cal(v[j].len));
      else
        v[j] = v[j].itg(0);
    }
    nv.clear();
    vector<int> buf;
    buf.clear();
    buf.push_back(0);
    nv.push_back(func(0, buf));
    for (int j = (0); j < (int)(v.size()); ++j) nv.push_back(v[j] >> PW);
    int i1 = 0, i2 = 0;
    tv.clear();
    while (1) {
      tv.push_back(v[i1] - nv[i2]);
      if (i1 + 1 == v.size() && i2 + 1 == nv.size()) break;
      if (i1 + 1 < v.size() &&
          (i2 + 1 == nv.size() || v[i1 + 1].len <= nv[i2 + 1].len))
        i1++;
      else
        i2++;
    }
    v.clear();
    for (int i = (0); i < (int)(tv.size()); ++i)
      if (i + 1 == tv.size() || tv[i].len < tv[i + 1].len) v.push_back(tv[i]);
    int id = -1;
    for (int j = (0); j < (int)(v.size()); ++j)
      if (v[j].len < lim) id = j;
    int p = v[id].cal(lim);
    v.resize(id + 1);
    buf.clear();
    buf.push_back(p);
    v.push_back(func(lim, buf));
  }
  cout << v[(int)(v.size()) - 1].cal(1000000000) << endl;
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
const long long PW = 1000000;
long long inv;
long long quickpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * quickpow(1ll * x * x % 998244353, k >> 1) *
                      (k & 1 ? x : 1) % 998244353;
}
int C[101][101];
struct func {
  vector<int> v;
  int len;
  func() {}
  func(int len, vector<int> v) : len(len), v(v) {}
  long long cal(int x) {
    int ret = 0, base = 1;
    for (int i = (0); i < (int)(v.size()); ++i)
      ret = (ret + 1ll * v[i] * base) % 998244353,
      base = 1ll * base * x % 998244353;
    return ret;
  }
  func itg(long long coef) {
    func ret;
    ret.len = len;
    ret.v.push_back(0);
    for (int i = (0); i < (int)(v.size()); ++i)
      ret.v.push_back(1ll * v[i] * quickpow(i + 1, 998244353 - 2) % 998244353 *
                      inv % 998244353);
    ret.v[0] = (998244353 - ret.cal(len) + coef) % 998244353;
    return ret;
  }
  func operator-(const func &t) const {
    func ret;
    ret.len = max(len, t.len);
    ret.v.resize(max(v.size(), t.v.size()));
    for (int i = (0); i < (int)(ret.v.size()); ++i) {
      int x = 0;
      if (i < v.size()) x += v[i];
      if (i < t.v.size()) x -= t.v[i];
      ret.v[i] = (x + 998244353) % 998244353;
    }
    return ret;
  }
  func operator>>(int x) {
    func ret;
    int pw[100];
    pw[0] = 1;
    for (int j = (1); j < (int)(v.size() + 1); ++j)
      pw[j] = 1ll * pw[j - 1] * (998244353 - x % 998244353) % 998244353;
    ret.len = len + x;
    ret.v.resize(v.size());
    for (int i = (0); i < (int)(v.size()); ++i) {
      if (v[i] == 0) continue;
      for (int j = (0); j < (int)(i + 1); ++j)
        ret.v[j] = (ret.v[j] + 1ll * C[i][j] * pw[i - j] % 998244353 * v[i]) %
                   998244353;
    }
    return ret;
  }
};
vector<func> v, nv, tv;
long long lm[33];
int main() {
  for (int i = (0); i < (int)(101); ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = (1); j < (int)(i); ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 998244353;
  }
  inv = quickpow(PW, 998244353 - 2);
  vector<int> buf;
  buf.clear();
  buf.push_back(1);
  v.push_back(func(0, buf));
  int n;
  cin >> n;
  for (int i = (0); i < (int)(n); ++i) {
    double x;
    cin >> x;
    lm[i] = int(x * PW + 0.5);
  }
  for (int i = (int)(n - 1) - 1; i >= 0; --i)
    lm[i] = (lm[i] < lm[i + 1] ? lm[i] : lm[i + 1]);
  for (int i = (0); i < (int)(n); ++i) {
    int lim = lm[i];
    for (int j = (0); j < (int)(v.size()); ++j) {
      if (j > 0)
        v[j] = v[j].itg(v[j - 1].cal(v[j].len));
      else
        v[j] = v[j].itg(0);
    }
    nv.clear();
    vector<int> buf;
    buf.clear();
    buf.push_back(0);
    nv.push_back(func(0, buf));
    for (int j = (0); j < (int)(v.size()); ++j) nv.push_back(v[j] >> PW);
    int i1 = 0, i2 = 0;
    tv.clear();
    while (1) {
      tv.push_back(v[i1] - nv[i2]);
      if (i1 + 1 == v.size() && i2 + 1 == nv.size()) break;
      if (i1 + 1 < v.size() &&
          (i2 + 1 == nv.size() || v[i1 + 1].len <= nv[i2 + 1].len))
        i1++;
      else
        i2++;
    }
    v.clear();
    for (int i = (0); i < (int)(tv.size()); ++i)
      if (i + 1 == tv.size() || tv[i].len < tv[i + 1].len) v.push_back(tv[i]);
    int id = -1;
    for (int j = (0); j < (int)(v.size()); ++j)
      if (v[j].len < lim) id = j;
    int p = v[id].cal(lim);
    v.resize(id + 1);
    buf.clear();
    buf.push_back(p);
    v.push_back(func(lim, buf));
  }
  cout << v[(int)(v.size()) - 1].cal(1000000000) << endl;
  return 0;
}

```