#include <bits/stdc++.h>
using namespace std;
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : (-a);
}
template <typename T>
void UMIN(T &a, T b) {
  if (b < a) a = b;
}
template <typename T>
void UMAX(T &a, T b) {
  if (b > a) a = b;
}
int M(int A, int B) {
  return ((long long)A * (long long)B) % (long long)998244353LL;
}
int powM(int A, int B) {
  int ret = 1;
  while (B) {
    if (B & 1) ret = M(ret, A);
    A = M(A, A);
    B >>= 1;
  }
  return ret;
}
int inv[1000005], id, iv;
struct poly {
  vector<int> coe;
  int eval(int v) {
    int ret = 0, cur = 1, i;
    for (i = 0; i < (int)coe.size(); ++i) {
      ret = (ret + M(coe[i], cur)) % 998244353LL;
      cur = M(cur, v);
    }
    return ret;
  }
  poly inte() {
    poly ret;
    ret.coe.clear();
    ret.coe.resize(coe.size() + 1);
    int i;
    for (i = 0; i < (int)coe.size(); ++i) {
      ret.coe[i + 1] = M(coe[i], inv[i + 1]);
    }
    return ret;
  }
  void zero() { coe.clear(); }
  void one() {
    coe.resize(1);
    coe[0] = 1;
  }
} tmp;
int n, X[35], C[35][35];
double x[35];
struct func {
  vector<poly> segs;
  vector<int> ptrs;
  void inte() {
    int i, j;
    for (i = 0; i < (int)segs.size(); ++i) {
      segs[i] = segs[i].inte();
      segs[i].coe[0] += 998244353LL - segs[i].eval(i ? M(ptrs[i - 1], id) : 0);
      segs[i].coe[0] %= 998244353LL;
    }
    int sum = (segs[0].eval(M(ptrs[0], id)) + 998244353LL - segs[0].eval(0)) %
              998244353LL;
    for (i = 1; i < (int)segs.size(); ++i) {
      if (segs[i].coe.empty()) segs[i].coe.resize(1);
      segs[i].coe[0] += sum;
      segs[i].coe[0] %= 998244353LL;
      sum += (segs[i].eval(M(ptrs[i], id)) + 998244353LL -
              segs[i].eval(M(ptrs[i - 1], id))) %
             998244353LL;
      sum %= 998244353LL;
    }
  }
  void minus_shift_1() {
    int i, j, k, p;
    for (i = (int)segs.size() - 1; i > 0; --i) {
      for (p = i - 1; p >= 0; --p) {
        if (ptrs[p] + iv <= ptrs[i]) break;
      }
      if (p < 0) continue;
      for (j = 0; j < (int)segs[p].coe.size(); ++j) {
        for (k = 0; k <= j; ++k) {
          if (k == (int)segs[i].coe.size()) segs[i].coe.push_back(0);
          if ((j - k) & 1)
            segs[i].coe[k] += M(segs[p].coe[j], C[j][k]);
          else
            segs[i].coe[k] += 998244353LL - M(segs[p].coe[j], C[j][k]);
          segs[i].coe[k] %= 998244353LL;
        }
      }
    }
  }
  void umin_with_v(int v) {
    int i, j, f;
    for (i = 0; i < (int)ptrs.size(); ++i) {
      if (ptrs[i] == v) break;
    }
    f = segs[i].eval(M(v, id));
    for (j = i + 1; j < (int)segs.size(); ++j) {
      segs[j].coe.clear();
      segs[j].coe.push_back(f);
    }
  }
} cur;
void precal() {
  int i, j, k;
  for (i = 1; i <= 1000000; ++i) inv[i] = powM(i, 998244353LL - 2);
  id = inv[1000000];
  iv = 1000000;
  for (i = 0; i < 35; ++i) C[i][0] = 1;
  for (i = 1; i < 35; ++i) {
    for (j = 1; j < 35; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 998244353LL;
    }
  }
}
int main() {
  int i, j, k;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%lf", x + i);
    X[i] = (1e6 * x[i] + 0.5);
  }
  precal();
  cur.ptrs.clear();
  for (i = 1; i <= n + 2; ++i) cur.ptrs.push_back(i * iv);
  for (i = 0; i < n; ++i) {
    int cv = X[i];
    while (cv > 0) {
      cur.ptrs.push_back(cv);
      cv -= iv;
    }
    for (j = 1; j <= n; ++j) {
      cur.ptrs.push_back(X[i] + j * iv);
    }
  }
  sort(cur.ptrs.begin(), cur.ptrs.end());
  cur.ptrs.erase(unique(cur.ptrs.begin(), cur.ptrs.end()), cur.ptrs.end());
  cur.segs.resize(cur.ptrs.size());
  for (i = 0; i < (int)cur.ptrs.size(); ++i) {
    if (cur.ptrs[i] <= iv) {
      cur.segs[i].coe.resize(2);
      cur.segs[i].coe[0] = 0;
      cur.segs[i].coe[1] = 1;
    } else
      cur.segs[i].one();
  }
  cur.umin_with_v(X[0]);
  for (i = 1; i < n; ++i) {
    cur.inte();
    cur.minus_shift_1();
    cur.umin_with_v(X[i]);
  }
  for (i = 0; i < (int)cur.segs.size(); ++i) {
    if (cur.ptrs[i] == X[n - 1]) {
      printf("%d\n", cur.segs[i].eval(M(X[n - 1], id)));
    }
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nTaken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : (-a);
}
template <typename T>
void UMIN(T &a, T b) {
  if (b < a) a = b;
}
template <typename T>
void UMAX(T &a, T b) {
  if (b > a) a = b;
}
int M(int A, int B) {
  return ((long long)A * (long long)B) % (long long)998244353LL;
}
int powM(int A, int B) {
  int ret = 1;
  while (B) {
    if (B & 1) ret = M(ret, A);
    A = M(A, A);
    B >>= 1;
  }
  return ret;
}
int inv[1000005], id, iv;
struct poly {
  vector<int> coe;
  int eval(int v) {
    int ret = 0, cur = 1, i;
    for (i = 0; i < (int)coe.size(); ++i) {
      ret = (ret + M(coe[i], cur)) % 998244353LL;
      cur = M(cur, v);
    }
    return ret;
  }
  poly inte() {
    poly ret;
    ret.coe.clear();
    ret.coe.resize(coe.size() + 1);
    int i;
    for (i = 0; i < (int)coe.size(); ++i) {
      ret.coe[i + 1] = M(coe[i], inv[i + 1]);
    }
    return ret;
  }
  void zero() { coe.clear(); }
  void one() {
    coe.resize(1);
    coe[0] = 1;
  }
} tmp;
int n, X[35], C[35][35];
double x[35];
struct func {
  vector<poly> segs;
  vector<int> ptrs;
  void inte() {
    int i, j;
    for (i = 0; i < (int)segs.size(); ++i) {
      segs[i] = segs[i].inte();
      segs[i].coe[0] += 998244353LL - segs[i].eval(i ? M(ptrs[i - 1], id) : 0);
      segs[i].coe[0] %= 998244353LL;
    }
    int sum = (segs[0].eval(M(ptrs[0], id)) + 998244353LL - segs[0].eval(0)) %
              998244353LL;
    for (i = 1; i < (int)segs.size(); ++i) {
      if (segs[i].coe.empty()) segs[i].coe.resize(1);
      segs[i].coe[0] += sum;
      segs[i].coe[0] %= 998244353LL;
      sum += (segs[i].eval(M(ptrs[i], id)) + 998244353LL -
              segs[i].eval(M(ptrs[i - 1], id))) %
             998244353LL;
      sum %= 998244353LL;
    }
  }
  void minus_shift_1() {
    int i, j, k, p;
    for (i = (int)segs.size() - 1; i > 0; --i) {
      for (p = i - 1; p >= 0; --p) {
        if (ptrs[p] + iv <= ptrs[i]) break;
      }
      if (p < 0) continue;
      for (j = 0; j < (int)segs[p].coe.size(); ++j) {
        for (k = 0; k <= j; ++k) {
          if (k == (int)segs[i].coe.size()) segs[i].coe.push_back(0);
          if ((j - k) & 1)
            segs[i].coe[k] += M(segs[p].coe[j], C[j][k]);
          else
            segs[i].coe[k] += 998244353LL - M(segs[p].coe[j], C[j][k]);
          segs[i].coe[k] %= 998244353LL;
        }
      }
    }
  }
  void umin_with_v(int v) {
    int i, j, f;
    for (i = 0; i < (int)ptrs.size(); ++i) {
      if (ptrs[i] == v) break;
    }
    f = segs[i].eval(M(v, id));
    for (j = i + 1; j < (int)segs.size(); ++j) {
      segs[j].coe.clear();
      segs[j].coe.push_back(f);
    }
  }
} cur;
void precal() {
  int i, j, k;
  for (i = 1; i <= 1000000; ++i) inv[i] = powM(i, 998244353LL - 2);
  id = inv[1000000];
  iv = 1000000;
  for (i = 0; i < 35; ++i) C[i][0] = 1;
  for (i = 1; i < 35; ++i) {
    for (j = 1; j < 35; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 998244353LL;
    }
  }
}
int main() {
  int i, j, k;
  scanf("%d", &n);
  for (i = 0; i < n; ++i) {
    scanf("%lf", x + i);
    X[i] = (1e6 * x[i] + 0.5);
  }
  precal();
  cur.ptrs.clear();
  for (i = 1; i <= n + 2; ++i) cur.ptrs.push_back(i * iv);
  for (i = 0; i < n; ++i) {
    int cv = X[i];
    while (cv > 0) {
      cur.ptrs.push_back(cv);
      cv -= iv;
    }
    for (j = 1; j <= n; ++j) {
      cur.ptrs.push_back(X[i] + j * iv);
    }
  }
  sort(cur.ptrs.begin(), cur.ptrs.end());
  cur.ptrs.erase(unique(cur.ptrs.begin(), cur.ptrs.end()), cur.ptrs.end());
  cur.segs.resize(cur.ptrs.size());
  for (i = 0; i < (int)cur.ptrs.size(); ++i) {
    if (cur.ptrs[i] <= iv) {
      cur.segs[i].coe.resize(2);
      cur.segs[i].coe[0] = 0;
      cur.segs[i].coe[1] = 1;
    } else
      cur.segs[i].one();
  }
  cur.umin_with_v(X[0]);
  for (i = 1; i < n; ++i) {
    cur.inte();
    cur.minus_shift_1();
    cur.umin_with_v(X[i]);
  }
  for (i = 0; i < (int)cur.segs.size(); ++i) {
    if (cur.ptrs[i] == X[n - 1]) {
      printf("%d\n", cur.segs[i].eval(M(X[n - 1], id)));
    }
  }
  return 0;
}

```