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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int N = 40;
int n;
long long val[N], comb[N][N], inv[N];
double p[N];
map<int, vector<long long> > dp[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n + 1; i++) {
    scanf("%lf", p + i);
    val[i] = p[i] * 1000000 + 0.1;
    inv[i] = powmod(i, mod - 2);
  }
  dp[n][val[n]] = vector<long long>{0};
  dp[n][0] = vector<long long>{1};
  for (int i = 0; i < n + 1; i++) {
    comb[i][0] = comb[i][i] = 1;
    for (int j = 1; j < i; j++)
      comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
  }
  for (int i = n - 1; i >= 1; i--) {
    vector<int> cand;
    for (auto p : dp[i + 1])
      cand.push_back(p.first), cand.push_back(max(0, p.first - 1000000));
    cand.push_back(val[i]);
    sort((cand).begin(), (cand).end());
    cand.erase(unique((cand).begin(), (cand).end()), cand.end());
    for (auto p : cand) {
      if (p == val[i]) {
        dp[i][p] = vector<long long>(n - i + 1, 0);
        break;
      } else {
        int x = p;
        int y = p + 1000000;
        vector<long long> c = vector<long long>(n - i + 1, 0);
        for (auto it = dp[i + 1].begin(); it != dp[i + 1].end(); it++) {
          auto nit = it;
          ++nit;
          int l = it->first;
          int r = 1 << 30;
          auto pol = it->second;
          if (nit != dp[i + 1].end()) r = nit->first;
          int vl = l * powmod(1000000, mod - 2) % mod,
              vr = r * powmod(1000000, mod - 2) % mod;
          if (x < l && r <= y) {
            for (int j = 0; j < ((int)(pol).size()); j++)
              c[0] = (c[0] + pol[j] * (powmod(vr, j + 1) - powmod(vl, j + 1)) %
                                 mod * inv[j + 1]) %
                     mod;
          } else if (r <= x || y < l) {
            continue;
          } else if (r <= y) {
            for (int j = 0; j < ((int)(pol).size()); j++)
              c[0] =
                  (c[0] + pol[j] * powmod(vr, j + 1) % mod * inv[j + 1]) % mod,
              c[j + 1] = (c[j + 1] - pol[j] * inv[j + 1]) % mod;
          } else if (x < l) {
            for (int j = 0; j < ((int)(pol).size()); j++) {
              c[0] =
                  (c[0] - pol[j] * powmod(vl, j + 1) % mod * inv[j + 1]) % mod;
              long long coef = pol[j] * inv[j + 1] % mod;
              for (int k = 0; k < j + 2; k++)
                c[k] = (c[k] + coef * comb[j + 1][k]) % mod;
            }
          } else {
            for (int j = 0; j < ((int)(pol).size()); j++) {
              long long coef = pol[j] * inv[j + 1] % mod;
              for (int k = 0; k < j + 2; k++)
                c[k] = (c[k] + coef * comb[j + 1][k]) % mod;
              c[j + 1] = (c[j + 1] - coef) % mod;
            }
          }
        }
        dp[i][x] = c;
      }
    }
    dp[i + 1].clear();
  }
  long long prob = 0;
  for (auto it = dp[1].begin(); it != dp[1].end(); it++) {
    auto nit = it;
    ++nit;
    int l = it->first;
    int r = 1 << 30;
    auto pol = it->second;
    if (nit != dp[1].end())
      r = nit->first;
    else
      break;
    if (l >= 1000000) break;
    r = min(r, 1000000);
    int vl = l * powmod(1000000, mod - 2) % mod,
        vr = r * powmod(1000000, mod - 2) % mod;
    for (int j = 0; j < ((int)(pol).size()); j++)
      prob = (prob + pol[j] * (powmod(vr, j + 1) - powmod(vl, j + 1)) % mod *
                         inv[j + 1]) %
             mod;
  }
  if (prob < 0) prob += mod;
  printf("%lld\n", prob);
}