#include <bits/stdc++.h>
const long long MOD = 998244353;
long long POWER(long long a, long long b) {
  long long r = 1;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a % MOD;
    a = a * a % MOD;
  }
  return r;
}
int N, L;
long long inv[31], start[3001], formula[3001][31];
int degree[3001];
void print() {
  for (int i = 0; i <= L; i++) {
    printf("start = %lld  formula =", start[i]);
    for (int j = degree[i]; j >= 0; j--) printf(" %lld", formula[i][j]);
    putchar(10);
  }
}
void integral() {
  long long before = 0;
  for (int i = 0; i <= L; i++) {
    for (int j = degree[i]; j >= 0; j--)
      formula[i][j + 1] = formula[i][j] * inv[j + 1] % MOD;
    degree[i]++;
    formula[i][0] = before;
    long long POW = MOD - 1;
    for (int j = 1; j <= degree[i]; j++) {
      POW = POW * start[i] % MOD;
      formula[i][0] = (formula[i][0] + formula[i][j] * POW) % MOD;
    }
    if (i < L) {
      before = 0;
      for (int j = degree[i]; j >= 0; j--)
        before = (before * start[i + 1] + formula[i][j]) % MOD;
    }
  }
}
void subtract(long long *F, int &n, long long *G, int m, long long dis) {
  static long long T[31];
  T[0] = G[m];
  for (int i = m - 1; i >= 0; i--) {
    T[m - i] = 0;
    for (int j = m - i - 1; j >= 0; j--) {
      T[j + 1] = (T[j + 1] + T[j]) % MOD;
      T[j] = T[j] * (MOD - dis) % MOD;
    }
    T[0] = (T[0] + G[i]) % MOD;
  }
  while (n < m) F[++n] = 0;
  for (int i = 0; i <= m; i++) F[i] = (F[i] - T[i] + MOD) % MOD;
}
void subtract(long long dis) {
  static long long new_start[3001];
  int new_L = -1;
  for (int i = 0, j = 0; i <= L || j <= L;)
    if (i <= L && j <= L && start[i] == start[j] + dis)
      new_start[++new_L] = start[i++], j++;
    else if (i <= L && (j > L || start[i] < start[j] + dis))
      new_start[++new_L] = start[i++];
    else
      new_start[++new_L] = start[j++] + dis;
  for (int i = new_L, j = L; i >= 0; i--) {
    while (start[j] > new_start[i]) j--;
    std::copy(formula[j], formula[j] + degree[j] + 1, formula[i]);
    degree[i] = degree[j];
  }
  L = new_L;
  std::copy(new_start, new_start + new_L + 1, start);
  for (int i = L, j = L; i >= 0 && start[i] >= dis; i--) {
    while (start[j] > start[i] - dis) j--;
    subtract(formula[i], degree[i], formula[j], degree[j], dis);
  }
}
void cut(long long lim) {
  while (L && start[L] >= lim) L--;
  long long C = 0;
  for (int i = degree[L]; i >= 0; i--) C = (C * lim + formula[L][i]) % MOD;
  start[++L] = lim;
  formula[L][0] = C;
  degree[L] = 0;
}
int main() {
  formula[0][0] = 1;
  scanf("%d", &N);
  inv[1] = 1;
  for (int i = 2; i <= N; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= N; i++) {
    double x;
    scanf("%lf", &x);
    integral();
    subtract(1000000);
    cut(x * 1000000 + 0.5);
  }
  printf("%lld\n", formula[L][0] * POWER(POWER(1000000, N), MOD - 2) % MOD);
  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>
const long long MOD = 998244353;
long long POWER(long long a, long long b) {
  long long r = 1;
  for (; b; b >>= 1) {
    if (b & 1) r = r * a % MOD;
    a = a * a % MOD;
  }
  return r;
}
int N, L;
long long inv[31], start[3001], formula[3001][31];
int degree[3001];
void print() {
  for (int i = 0; i <= L; i++) {
    printf("start = %lld  formula =", start[i]);
    for (int j = degree[i]; j >= 0; j--) printf(" %lld", formula[i][j]);
    putchar(10);
  }
}
void integral() {
  long long before = 0;
  for (int i = 0; i <= L; i++) {
    for (int j = degree[i]; j >= 0; j--)
      formula[i][j + 1] = formula[i][j] * inv[j + 1] % MOD;
    degree[i]++;
    formula[i][0] = before;
    long long POW = MOD - 1;
    for (int j = 1; j <= degree[i]; j++) {
      POW = POW * start[i] % MOD;
      formula[i][0] = (formula[i][0] + formula[i][j] * POW) % MOD;
    }
    if (i < L) {
      before = 0;
      for (int j = degree[i]; j >= 0; j--)
        before = (before * start[i + 1] + formula[i][j]) % MOD;
    }
  }
}
void subtract(long long *F, int &n, long long *G, int m, long long dis) {
  static long long T[31];
  T[0] = G[m];
  for (int i = m - 1; i >= 0; i--) {
    T[m - i] = 0;
    for (int j = m - i - 1; j >= 0; j--) {
      T[j + 1] = (T[j + 1] + T[j]) % MOD;
      T[j] = T[j] * (MOD - dis) % MOD;
    }
    T[0] = (T[0] + G[i]) % MOD;
  }
  while (n < m) F[++n] = 0;
  for (int i = 0; i <= m; i++) F[i] = (F[i] - T[i] + MOD) % MOD;
}
void subtract(long long dis) {
  static long long new_start[3001];
  int new_L = -1;
  for (int i = 0, j = 0; i <= L || j <= L;)
    if (i <= L && j <= L && start[i] == start[j] + dis)
      new_start[++new_L] = start[i++], j++;
    else if (i <= L && (j > L || start[i] < start[j] + dis))
      new_start[++new_L] = start[i++];
    else
      new_start[++new_L] = start[j++] + dis;
  for (int i = new_L, j = L; i >= 0; i--) {
    while (start[j] > new_start[i]) j--;
    std::copy(formula[j], formula[j] + degree[j] + 1, formula[i]);
    degree[i] = degree[j];
  }
  L = new_L;
  std::copy(new_start, new_start + new_L + 1, start);
  for (int i = L, j = L; i >= 0 && start[i] >= dis; i--) {
    while (start[j] > start[i] - dis) j--;
    subtract(formula[i], degree[i], formula[j], degree[j], dis);
  }
}
void cut(long long lim) {
  while (L && start[L] >= lim) L--;
  long long C = 0;
  for (int i = degree[L]; i >= 0; i--) C = (C * lim + formula[L][i]) % MOD;
  start[++L] = lim;
  formula[L][0] = C;
  degree[L] = 0;
}
int main() {
  formula[0][0] = 1;
  scanf("%d", &N);
  inv[1] = 1;
  for (int i = 2; i <= N; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= N; i++) {
    double x;
    scanf("%lf", &x);
    integral();
    subtract(1000000);
    cut(x * 1000000 + 0.5);
  }
  printf("%lld\n", formula[L][0] * POWER(POWER(1000000, N), MOD - 2) % MOD);
  return 0;
}

```