#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int K = 1000000;
int iK;
const int N = 33, M = 2010, maxn = 30;
int f[M][N], g[M][N], h[M][N];
int R[M], tot, b[M], cnt;
int cur;
int c[N][N], inv[N];
int wl[M], wr[M], s[M];
int a[M];
int power(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1ll * x * x % mod) {
    if (y & 1) ret = 1ll * ret * x % mod;
  }
  return ret;
}
void integral(int id) {
  int i, j;
  for (i = 1; i <= cur; i++) g[id][i] = 1ll * f[id][i - 1] * inv[i] % mod;
  g[id][0] = 0;
  memset(h[id], 0, sizeof(h[id]));
  for (i = 1; i <= cur; i++)
    for (j = 0; j <= i; j++)
      h[id][j] = (h[id][j] + 1ll * g[id][i] * c[i][j]) % mod;
}
int eval(int a[], int x) {
  int ret = 0;
  int i, j;
  for (i = 0, j = 1; i <= cur; i++, j = 1ll * j * x % mod)
    ret = (ret + 1ll * j * a[i]) % mod;
  return ret;
}
void work() {
  int l, r, i, j;
  memset(f[tot + 1], 0, sizeof(f[tot + 1]));
  R[tot + 1] = R[tot] + K;
  for (i = 1; i <= tot + 1; i++) integral(i);
  for (i = 1; i <= tot + 1; i++) {
    wl[i] = eval(g[i], 1ll * R[i - 1] * iK % mod);
    wr[i] = eval(g[i], 1ll * R[i] * iK % mod);
    s[i] = (wr[i] - wl[i] + mod) % mod;
  }
  for (i = 1; i <= tot + 1; i++) (s[i] += s[i - 1]) %= mod;
  cnt = 0;
  for (i = 1; i <= tot; i++) b[++cnt] = R[i];
  for (i = 1; i <= tot; i++) b[++cnt] = R[i] + K;
  b[++cnt] = K;
  sort(b + 1, b + 1 + cnt);
  cnt = unique(b + 1, b + 1 + cnt) - b - 1;
  l = r = 0;
  for (i = 1; i <= cnt; i++) {
    while (R[l] < b[i] - K) l++;
    while (R[r] < b[i]) r++;
    memset(f[i], 0, sizeof(f[i]));
    f[i][0] = (1ll * s[r - 1] - s[l] + wr[l] - wl[r] + mod + mod) % mod;
    for (j = 0; j <= cur; j++) f[i][j] = (f[i][j] + g[r][j]) % mod;
    for (j = 0; j <= cur; j++) f[i][j] = (f[i][j] - h[l][j] + mod) % mod;
  }
  tot = cnt;
  for (i = 1; i <= tot; i++) R[i] = b[i];
  if (R[tot] < a[cur]) return;
  while (R[tot] >= a[cur]) tot--;
  R[++tot] = a[cur];
}
void calc() {
  int i;
  for (i = 1; i <= tot; i++) integral(i);
  for (i = 1; i <= tot; i++) {
    wl[i] = eval(g[i], 1ll * R[i - 1] * iK % mod);
    wr[i] = eval(g[i], 1ll * R[i] * iK % mod);
    s[i] = (wr[i] - wl[i] + mod) % mod;
  }
  for (i = 1; i <= tot; i++) (s[i] += s[i - 1]) %= mod;
  printf("%d\n", s[tot]);
}
void init() {
  int i, j;
  iK = power(K, mod - 2);
  inv[1] = 1;
  for (i = 2; i <= maxn; i++)
    inv[i] = (-1ll * (mod / i) * inv[mod % i] % mod + mod) % mod;
  for (i = 0; i <= maxn; i++)
    for (c[i][0] = 1, j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  for (i = 0; i <= maxn; i++)
    for (j = 0; j <= i; j++) c[i][j] = (i - j & 1) ? mod - c[i][j] : c[i][j];
}
int main() {
  int n, i;
  double dx;
  int j;
  init();
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lf", &dx);
    a[i] = (int)(dx * (double)K * 10 + 0.5) / 10;
  }
  tot = 1;
  f[tot][0] = 1;
  R[tot] = min(K, a[1]);
  for (cur = 2; cur <= n; cur++) work();
  calc();
}

### Prompt

Please create a solution in CPP to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int K = 1000000;
int iK;
const int N = 33, M = 2010, maxn = 30;
int f[M][N], g[M][N], h[M][N];
int R[M], tot, b[M], cnt;
int cur;
int c[N][N], inv[N];
int wl[M], wr[M], s[M];
int a[M];
int power(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1ll * x * x % mod) {
    if (y & 1) ret = 1ll * ret * x % mod;
  }
  return ret;
}
void integral(int id) {
  int i, j;
  for (i = 1; i <= cur; i++) g[id][i] = 1ll * f[id][i - 1] * inv[i] % mod;
  g[id][0] = 0;
  memset(h[id], 0, sizeof(h[id]));
  for (i = 1; i <= cur; i++)
    for (j = 0; j <= i; j++)
      h[id][j] = (h[id][j] + 1ll * g[id][i] * c[i][j]) % mod;
}
int eval(int a[], int x) {
  int ret = 0;
  int i, j;
  for (i = 0, j = 1; i <= cur; i++, j = 1ll * j * x % mod)
    ret = (ret + 1ll * j * a[i]) % mod;
  return ret;
}
void work() {
  int l, r, i, j;
  memset(f[tot + 1], 0, sizeof(f[tot + 1]));
  R[tot + 1] = R[tot] + K;
  for (i = 1; i <= tot + 1; i++) integral(i);
  for (i = 1; i <= tot + 1; i++) {
    wl[i] = eval(g[i], 1ll * R[i - 1] * iK % mod);
    wr[i] = eval(g[i], 1ll * R[i] * iK % mod);
    s[i] = (wr[i] - wl[i] + mod) % mod;
  }
  for (i = 1; i <= tot + 1; i++) (s[i] += s[i - 1]) %= mod;
  cnt = 0;
  for (i = 1; i <= tot; i++) b[++cnt] = R[i];
  for (i = 1; i <= tot; i++) b[++cnt] = R[i] + K;
  b[++cnt] = K;
  sort(b + 1, b + 1 + cnt);
  cnt = unique(b + 1, b + 1 + cnt) - b - 1;
  l = r = 0;
  for (i = 1; i <= cnt; i++) {
    while (R[l] < b[i] - K) l++;
    while (R[r] < b[i]) r++;
    memset(f[i], 0, sizeof(f[i]));
    f[i][0] = (1ll * s[r - 1] - s[l] + wr[l] - wl[r] + mod + mod) % mod;
    for (j = 0; j <= cur; j++) f[i][j] = (f[i][j] + g[r][j]) % mod;
    for (j = 0; j <= cur; j++) f[i][j] = (f[i][j] - h[l][j] + mod) % mod;
  }
  tot = cnt;
  for (i = 1; i <= tot; i++) R[i] = b[i];
  if (R[tot] < a[cur]) return;
  while (R[tot] >= a[cur]) tot--;
  R[++tot] = a[cur];
}
void calc() {
  int i;
  for (i = 1; i <= tot; i++) integral(i);
  for (i = 1; i <= tot; i++) {
    wl[i] = eval(g[i], 1ll * R[i - 1] * iK % mod);
    wr[i] = eval(g[i], 1ll * R[i] * iK % mod);
    s[i] = (wr[i] - wl[i] + mod) % mod;
  }
  for (i = 1; i <= tot; i++) (s[i] += s[i - 1]) %= mod;
  printf("%d\n", s[tot]);
}
void init() {
  int i, j;
  iK = power(K, mod - 2);
  inv[1] = 1;
  for (i = 2; i <= maxn; i++)
    inv[i] = (-1ll * (mod / i) * inv[mod % i] % mod + mod) % mod;
  for (i = 0; i <= maxn; i++)
    for (c[i][0] = 1, j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  for (i = 0; i <= maxn; i++)
    for (j = 0; j <= i; j++) c[i][j] = (i - j & 1) ? mod - c[i][j] : c[i][j];
}
int main() {
  int n, i;
  double dx;
  int j;
  init();
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lf", &dx);
    a[i] = (int)(dx * (double)K * 10 + 0.5) / 10;
  }
  tot = 1;
  f[tot][0] = 1;
  R[tot] = min(K, a[1]);
  for (cur = 2; cur <= n; cur++) work();
  calc();
}

```