#include <bits/stdc++.h>
using namespace std;
const int N = 40;
const int mod = 998244353;
const int inf = 1e9;
const int M = 1e6;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
void inc(int &a, int b) { a = a + b >= mod ? a + b - mod : a + b; }
void dec(int &a, int b) { a = a - b < 0 ? a - b + mod : a - b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int qpow(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
int n, x[N], inv[N], C[N][N], pw_M[N], st[N * N], tp;
vector<int> operator+(vector<int> a, const vector<int> &b) {
  int n = int(a.size()), m = int(b.size());
  if (n < m) a.resize(m);
  for (int i = 0; i < m; i++) inc(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, const vector<int> &b) {
  int n = int(a.size()), m = int(b.size());
  if (n < m) a.resize(m);
  for (int i = 0; i < m; i++) dec(a[i], b[i]);
  return a;
}
int getval(const vector<int> &a, int x) {
  int n = int(a.size()), ret = 0;
  for (int i = 0, pw = 1; i < n; i++, pw = 1ll * pw * x % mod)
    ret = (ret + 1ll * a[i] * pw) % mod;
  return ret;
}
vector<int> shift(const vector<int> &a) {
  int n = int(a.size());
  vector<int> ret(n);
  for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
      ret[i] = (ret[i] + 1ll * a[j] * C[j][i] % mod * pw_M[j - i]) % mod;
  return ret;
}
vector<int> Int(vector<int> a) {
  int n = int(a.size());
  a.push_back(0);
  for (int i = n - 1; ~i; i--) a[i + 1] = 1ll * a[i] * inv[i + 1] % mod;
  a[0] = 0;
  return a;
}
int find(int x) { return lower_bound(st + 1, st + tp + 1, x) - st; }
vector<int> f[N * N], new_f[N * N];
void print() {
  for (int i = 1; i < tp; i++) {
    cerr << st[i] << ' ' << st[i + 1] << endl;
    for (auto t : f[i]) cerr << t << ' ';
    cerr << endl;
  }
  cerr << endl << endl;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    double tmp;
    cin >> tmp;
    x[i] = int(tmp * M + 0.5);
    for (int j = x[i] % M; j <= n * M; j += M) st[++tp] = j;
  }
  for (int i = 0; i <= n; i++) st[++tp] = i * M;
  sort(st + 1, st + tp + 1);
  tp = unique(st + 1, st + tp + 1) - st - 1;
  inv[1] = 1;
  for (int i = 2; i < N; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  pw_M[0] = 1;
  for (int i = 1; i < N; i++) pw_M[i] = 1ll * pw_M[i - 1] * (mod - M) % mod;
  for (int i = 1; i < tp; i++) {
    if (st[i + 1] <= x[1] && st[i + 1] <= M)
      f[i] = {1};
    else
      f[i] = {0};
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < N * N; j++) new_f[j] = {0};
    for (int j = 1; j < tp; j++) {
      vector<int> F = Int(f[j]);
      new_f[j] = F - vector<int>{getval(F, st[j])};
      for (int k = j - 1; k; k--) {
        vector<int> G = Int(f[k]);
        if (st[k] >= st[j + 1] - M)
          new_f[j] = new_f[j] +
                     vector<int>{sub(getval(G, st[k + 1]), getval(G, st[k]))};
        else {
          new_f[j] = new_f[j] + vector<int>{getval(G, st[k + 1])} - shift(G);
          break;
        }
      }
    }
    for (int j = 1; j < tp; j++)
      if (st[j + 1] > x[i]) new_f[j] = {0};
    swap(f, new_f);
  }
  int ans = 0;
  for (int i = 1; i < tp; i++) {
    vector<int> F = Int(f[i]);
    inc(ans, sub(getval(F, st[i + 1]), getval(F, st[i])));
  }
  for (int i = 1; i <= n; i++) ans = 1ll * ans * qpow(M, mod - 2) % mod;
  cout << 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;
const int N = 40;
const int mod = 998244353;
const int inf = 1e9;
const int M = 1e6;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
void inc(int &a, int b) { a = a + b >= mod ? a + b - mod : a + b; }
void dec(int &a, int b) { a = a - b < 0 ? a - b + mod : a - b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
int qpow(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
int n, x[N], inv[N], C[N][N], pw_M[N], st[N * N], tp;
vector<int> operator+(vector<int> a, const vector<int> &b) {
  int n = int(a.size()), m = int(b.size());
  if (n < m) a.resize(m);
  for (int i = 0; i < m; i++) inc(a[i], b[i]);
  return a;
}
vector<int> operator-(vector<int> a, const vector<int> &b) {
  int n = int(a.size()), m = int(b.size());
  if (n < m) a.resize(m);
  for (int i = 0; i < m; i++) dec(a[i], b[i]);
  return a;
}
int getval(const vector<int> &a, int x) {
  int n = int(a.size()), ret = 0;
  for (int i = 0, pw = 1; i < n; i++, pw = 1ll * pw * x % mod)
    ret = (ret + 1ll * a[i] * pw) % mod;
  return ret;
}
vector<int> shift(const vector<int> &a) {
  int n = int(a.size());
  vector<int> ret(n);
  for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
      ret[i] = (ret[i] + 1ll * a[j] * C[j][i] % mod * pw_M[j - i]) % mod;
  return ret;
}
vector<int> Int(vector<int> a) {
  int n = int(a.size());
  a.push_back(0);
  for (int i = n - 1; ~i; i--) a[i + 1] = 1ll * a[i] * inv[i + 1] % mod;
  a[0] = 0;
  return a;
}
int find(int x) { return lower_bound(st + 1, st + tp + 1, x) - st; }
vector<int> f[N * N], new_f[N * N];
void print() {
  for (int i = 1; i < tp; i++) {
    cerr << st[i] << ' ' << st[i + 1] << endl;
    for (auto t : f[i]) cerr << t << ' ';
    cerr << endl;
  }
  cerr << endl << endl;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    double tmp;
    cin >> tmp;
    x[i] = int(tmp * M + 0.5);
    for (int j = x[i] % M; j <= n * M; j += M) st[++tp] = j;
  }
  for (int i = 0; i <= n; i++) st[++tp] = i * M;
  sort(st + 1, st + tp + 1);
  tp = unique(st + 1, st + tp + 1) - st - 1;
  inv[1] = 1;
  for (int i = 2; i < N; i++)
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  pw_M[0] = 1;
  for (int i = 1; i < N; i++) pw_M[i] = 1ll * pw_M[i - 1] * (mod - M) % mod;
  for (int i = 1; i < tp; i++) {
    if (st[i + 1] <= x[1] && st[i + 1] <= M)
      f[i] = {1};
    else
      f[i] = {0};
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < N * N; j++) new_f[j] = {0};
    for (int j = 1; j < tp; j++) {
      vector<int> F = Int(f[j]);
      new_f[j] = F - vector<int>{getval(F, st[j])};
      for (int k = j - 1; k; k--) {
        vector<int> G = Int(f[k]);
        if (st[k] >= st[j + 1] - M)
          new_f[j] = new_f[j] +
                     vector<int>{sub(getval(G, st[k + 1]), getval(G, st[k]))};
        else {
          new_f[j] = new_f[j] + vector<int>{getval(G, st[k + 1])} - shift(G);
          break;
        }
      }
    }
    for (int j = 1; j < tp; j++)
      if (st[j + 1] > x[i]) new_f[j] = {0};
    swap(f, new_f);
  }
  int ans = 0;
  for (int i = 1; i < tp; i++) {
    vector<int> F = Int(f[i]);
    inc(ans, sub(getval(F, st[i + 1]), getval(F, st[i])));
  }
  for (int i = 1; i <= n; i++) ans = 1ll * ans * qpow(M, mod - 2) % mod;
  cout << ans;
  return 0;
}

```