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;
template <typename T>
T MAX(T a, T b) {
  return (a > b) ? a : b;
}
template <typename T>
T MIN(T a, T b) {
  return (a < b) ? a : b;
}
template <typename T>
void UMAX(T &a, T b) {
  a = (a > b ? a : b);
}
template <typename T>
void UMIN(T &a, T b) {
  a = (a < b ? a : b);
}
long long readint() {
  char c = getchar();
  long long ret = 0ll;
  bool neg = 0;
  while (!(c >= '0' && c <= '9')) {
    if (c == '-') neg = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ret = ret * 10ll + (long long)(c - '0');
    c = getchar();
  }
  return neg ? -ret : ret;
}
void putint(long long v) {
  if (v < 0) {
    putchar('-');
    v = -v;
  }
  if (!v) {
    putchar('0');
    return;
  }
  if (v >= 10ll) putint(v / 10ll);
  putchar('0' + (v % 10ll));
}
const int MOD = 998244353, unilen = 1000000;
int inv[55], C[55][55], pwu[55], invu;
int powM(int V, int T = MOD - 2) {
  int R = 1;
  while (T) {
    if (T & 1) R = (long long)R * V % MOD;
    T >>= 1;
    V = (long long)V * V % MOD;
  }
  return R;
}
struct poly {
  vector<int> coe;
  poly(int cons = 0) { coe.assign(1, cons); }
  int eval(int x) {
    int ret = 0, xp = 1, i;
    for (i = 0; i < (int)coe.size(); ++i) {
      ret = (ret + (long long)xp * coe[i]) % MOD;
      xp = (long long)xp * x % MOD;
    }
    return ret;
  }
  void multiply(int v) {
    int i;
    for (i = 0; i < (int)coe.size(); ++i) {
      coe[i] = (long long)coe[i] * v % MOD;
    }
  }
};
poly operator<<(poly A, int k) {
  A.coe.resize((int)A.coe.size() + k);
  int i;
  for (i = (int)A.coe.size() - 1; i >= k; --i) {
    A.coe[i] = A.coe[i - k];
  }
  fill(A.coe.begin(), A.coe.begin() + k, 0);
  return A;
}
poly operator+(poly A, const poly &B) {
  int i;
  if (A.coe.size() < B.coe.size()) A.coe.resize(B.coe.size());
  for (i = 0; i < (int)B.coe.size(); ++i) {
    A.coe[i] += B.coe[i];
    if (A.coe[i] >= MOD) A.coe[i] -= MOD;
  }
  return A;
}
poly operator-(poly A, const poly &B) {
  int i;
  if (A.coe.size() < B.coe.size()) A.coe.resize(B.coe.size());
  for (i = 0; i < (int)B.coe.size(); ++i) {
    A.coe[i] -= B.coe[i];
    if (A.coe[i] < 0) A.coe[i] += MOD;
  }
  return A;
}
poly integrate(poly A) {
  A = A << 1;
  int i;
  for (i = 1; i < (int)A.coe.size(); ++i) {
    A.coe[i] = (long long)A.coe[i] * inv[i] % MOD;
  }
  return A;
}
poly shiftbyunit(poly A) {
  int i, j;
  for (i = 0; i < (int)A.coe.size(); ++i) {
    for (j = i - 1; j >= 0; --j) {
      if ((i - j) & 1) {
        A.coe[j] -= (long long)A.coe[i] * C[i][j] % MOD * pwu[i - j] % MOD;
        if (A.coe[j] < 0) A.coe[j] += MOD;
      } else {
        A.coe[j] += (long long)A.coe[i] * C[i][j] % MOD * pwu[i - j] % MOD;
        if (A.coe[j] >= MOD) A.coe[j] -= MOD;
      }
    }
  }
  return A;
}
poly range_integrate_1(poly P, int l) {
  return integrate(P) - poly(integrate(P).eval(l));
}
poly range_integrate_2(poly P, int r) {
  return poly(integrate(P).eval(r)) - integrate(P);
}
int range_integrate_det(poly P, int l, int r) {
  return (integrate(P).eval(r) + MOD - integrate(P).eval(l)) % MOD;
}
struct polyseg {
  vector<poly> segs;
  vector<int> rbnd;
  polyseg() {
    segs.clear();
    rbnd.clear();
  }
  void truncate(int to) {
    if (segs.empty() || rbnd.back() <= to) return;
    while ((int)rbnd.size() > 1 && rbnd[(int)rbnd.size() - 2] >= to)
      rbnd.pop_back(), segs.pop_back();
    rbnd.back() = to;
  }
  void newele() {
    if (segs.empty()) {
      segs.push_back(poly(invu) << 1);
      rbnd.push_back(unilen);
      return;
    }
    int i, j;
    vector<int> nrbnd, tmp;
    tmp.push_back(unilen);
    for (i = 0; i < (int)rbnd.size(); ++i) {
      tmp.push_back(rbnd[i] + unilen);
    }
    merge(rbnd.begin(), rbnd.end(), tmp.begin(), tmp.end(),
          back_inserter(nrbnd));
    nrbnd.erase(unique(nrbnd.begin(), nrbnd.end()), nrbnd.end());
    vector<poly> nsegs(nrbnd.size());
    int ptr = 0;
    for (i = 0; i < (int)nrbnd.size(); ++i) {
      while (ptr < (int)rbnd.size() && rbnd[ptr] < nrbnd[i]) ++ptr;
      nsegs[i] = ptr < (int)rbnd.size() ? segs[ptr]
                                        : poly(segs.back().eval(rbnd.back()));
    }
    segs = nsegs;
    rbnd = nrbnd;
    for (i = (int)segs.size() - 1; i >= 0; --i) {
      int iL = i ? rbnd[i - 1] : 0, iR = rbnd[i];
      segs[i] = range_integrate_1(segs[i], iL);
      for (j = i - 1; j >= 0; --j) {
        int jL = j ? rbnd[j - 1] : 0, jR = rbnd[j];
        if (jL >= iR - unilen)
          segs[i] = segs[i] + poly(range_integrate_det(segs[j], jL, jR));
        else if (jR >= iR - unilen)
          segs[i] = segs[i] + shiftbyunit(range_integrate_2(segs[j], jR));
        else
          break;
      }
      segs[i].multiply(invu);
    }
  }
} res;
int main() {
  int i, j, k;
  for (i = 1; i <= 50; ++i) inv[i] = powM(i);
  for (i = 0; i <= 50; ++i) C[i][0] = 1;
  for (i = 0; i <= 50; ++i) pwu[i] = powM(unilen, i);
  invu = powM(unilen);
  for (i = 1; i <= 50; ++i)
    for (j = 1; j <= 50; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  int n = readint();
  for (i = 0; i < n; ++i) {
    double f;
    scanf("%lf", &f);
    res.newele();
    res.truncate((int)(f * unilen + 0.5));
  }
  printf("%d\n", res.segs.back().eval(res.rbnd.back()));
  return 0;
}