#include <bits/stdc++.h>
namespace modular {
using namespace std;
long long gcdExt(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long z, w;
  long long c = gcdExt(b, a % b, z, w);
  x = w;
  y = z - (a / b) * w;
  return c;
}
long long modInverse(long long a, long long p) {
  long long x, y;
  long long d = gcdExt(a, p, x, y);
  if (d != 1) return 0;
  return x >= 0 ? x % p : (x % p) + p;
}
template <int MOD_>
struct modnum {
  static constexpr int mod = MOD_;
  static_assert(MOD_ > 0, "MOD_ must be positive");
  int val;
  modnum() : val(0) {}
  modnum(int v) : val(v % mod) {
    if (val < 0) val = val + mod;
  }
  friend ostream& operator<<(ostream& out, const modnum& a) {
    return out << a.val;
  }
  friend bool operator==(const modnum& a, const modnum& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.val != b.val;
  }
  modnum operator-() const {
    int newval = val == 0 ? 0 : mod - val;
    return modnum(newval);
  }
  friend modnum inv(const modnum& a) {
    int newval = modInverse(a.val, mod);
    return modnum(newval);
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    int diff = (a.val - b.val);
    diff = diff >= 0 ? diff : diff + mod;
    return modnum(diff);
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    int sum = a.val - (mod - b.val);
    sum = sum >= 0 ? sum : sum + mod;
    return modnum(sum);
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    int prodVal = int((((long long)a.val) * ((long long)b.val)) % mod);
    return modnum(prodVal);
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return a * (inv(b));
  }
};
}  // namespace modular
using namespace modular;
using namespace std;
using num = modnum<1000000007>;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<num> as(n);
  map<int, int> log2;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    as[i] = num(a);
    log2[1 << i] = i;
  }
  int mask = 1 << n;
  vector<vector<num>> fromTo =
      vector<vector<num>>(n, vector<num>(mask, num(1)));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      fromTo[i][1 << j] = as[i] / (as[i] + as[j]);
    }
    for (int k = 1; k < mask; k++) {
      int l = k & (k - 1);
      fromTo[i][k] = fromTo[i][l] * fromTo[i][k ^ l];
    }
  }
  vector<num> connectedProb = vector<num>(mask, num(1));
  for (int m = 1; m < mask; m++) {
    if ((m & (m - 1)) == 0) continue;
    num curr = num(1);
    for (int s = (m - 1) & m; s; s = (s - 1) & m) {
      num product = connectedProb[s];
      int c = m ^ s;
      int u = s;
      while (u) {
        int v = u & (u - 1);
        int i = log2[u ^ v];
        product = product * fromTo[i][c];
        u = v;
      }
      curr = curr - product;
    }
    connectedProb[m] = curr;
  }
  int m = mask - 1;
  num ans = num(0);
  for (int s = m; s; s = (s - 1) & m) {
    num product = connectedProb[s];
    int c = m ^ s;
    int u = s;
    int count = 0;
    while (u) {
      count++;
      int v = u & (u - 1);
      int i = log2[u ^ v];
      product = product * fromTo[i][c];
      u = v;
    }
    product = product * count;
    ans = ans + product;
  }
  cout << ans << '\n';
}

### Prompt

Your task is to create a CPP solution to the following problem:

<image>

William is not only interested in trading but also in betting on sports matches. n teams participate in each match. Each team is characterized by strength a_i. Each two teams i < j play with each other exactly once. Team i wins with probability (a_i)/(a_i + a_j) and team j wins with probability (a_j)/(a_i + a_j).

The team is called a winner if it directly or indirectly defeated all other teams. Team a defeated (directly or indirectly) team b if there is a sequence of teams c_1, c_2, ... c_k such that c_1 = a, c_k = b and team c_i defeated team c_{i + 1} for all i from 1 to k - 1. Note that it is possible that team a defeated team b and in the same time team b defeated team a.

William wants you to find the expected value of the number of winners.

Input

The first line contains a single integer n (1 ≤ n ≤ 14), which is the total number of teams participating in a match.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6) — the strengths of teams participating in a match.

Output

Output a single integer — the expected value of the number of winners of the tournament modulo 10^9 + 7.

Formally, let M = 10^9+7. It can be demonstrated that the answer can be presented as a irreducible fraction p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output a single integer equal to p ⋅ q^{-1} mod M. In other words, output an integer x such that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.

Examples

Input


2
1 2


Output


1


Input


5
1 5 2 11 14


Output


642377629

Note

To better understand in which situation several winners are possible let's examine the second test:

One possible result of the tournament is as follows (a → b means that a defeated b):

  * 1 → 2 
  * 2 → 3 
  * 3 → 1 
  * 1 → 4 
  * 1 → 5 
  * 2 → 4 
  * 2 → 5 
  * 3 → 4 
  * 3 → 5 
  * 4 → 5 



Or more clearly in the picture:

<image>

In this case every team from the set \{ 1, 2, 3 \} directly or indirectly defeated everyone. I.e.:

  * 1st defeated everyone because they can get to everyone else in the following way 1 → 2, 1 → 2 → 3, 1 → 4, 1 → 5. 
  * 2nd defeated everyone because they can get to everyone else in the following way 2 → 3, 2 → 3 → 1, 2 → 4, 2 → 5. 
  * 3rd defeated everyone because they can get to everyone else in the following way 3 → 1, 3 → 1 → 2, 3 → 4, 3 → 5. 



Therefore the total number of winners is 3.

### Response

```cpp
#include <bits/stdc++.h>
namespace modular {
using namespace std;
long long gcdExt(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long z, w;
  long long c = gcdExt(b, a % b, z, w);
  x = w;
  y = z - (a / b) * w;
  return c;
}
long long modInverse(long long a, long long p) {
  long long x, y;
  long long d = gcdExt(a, p, x, y);
  if (d != 1) return 0;
  return x >= 0 ? x % p : (x % p) + p;
}
template <int MOD_>
struct modnum {
  static constexpr int mod = MOD_;
  static_assert(MOD_ > 0, "MOD_ must be positive");
  int val;
  modnum() : val(0) {}
  modnum(int v) : val(v % mod) {
    if (val < 0) val = val + mod;
  }
  friend ostream& operator<<(ostream& out, const modnum& a) {
    return out << a.val;
  }
  friend bool operator==(const modnum& a, const modnum& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const modnum& a, const modnum& b) {
    return a.val != b.val;
  }
  modnum operator-() const {
    int newval = val == 0 ? 0 : mod - val;
    return modnum(newval);
  }
  friend modnum inv(const modnum& a) {
    int newval = modInverse(a.val, mod);
    return modnum(newval);
  }
  friend modnum operator-(const modnum& a, const modnum& b) {
    int diff = (a.val - b.val);
    diff = diff >= 0 ? diff : diff + mod;
    return modnum(diff);
  }
  friend modnum operator+(const modnum& a, const modnum& b) {
    int sum = a.val - (mod - b.val);
    sum = sum >= 0 ? sum : sum + mod;
    return modnum(sum);
  }
  friend modnum operator*(const modnum& a, const modnum& b) {
    int prodVal = int((((long long)a.val) * ((long long)b.val)) % mod);
    return modnum(prodVal);
  }
  friend modnum operator/(const modnum& a, const modnum& b) {
    return a * (inv(b));
  }
};
}  // namespace modular
using namespace modular;
using namespace std;
using num = modnum<1000000007>;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<num> as(n);
  map<int, int> log2;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    as[i] = num(a);
    log2[1 << i] = i;
  }
  int mask = 1 << n;
  vector<vector<num>> fromTo =
      vector<vector<num>>(n, vector<num>(mask, num(1)));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      fromTo[i][1 << j] = as[i] / (as[i] + as[j]);
    }
    for (int k = 1; k < mask; k++) {
      int l = k & (k - 1);
      fromTo[i][k] = fromTo[i][l] * fromTo[i][k ^ l];
    }
  }
  vector<num> connectedProb = vector<num>(mask, num(1));
  for (int m = 1; m < mask; m++) {
    if ((m & (m - 1)) == 0) continue;
    num curr = num(1);
    for (int s = (m - 1) & m; s; s = (s - 1) & m) {
      num product = connectedProb[s];
      int c = m ^ s;
      int u = s;
      while (u) {
        int v = u & (u - 1);
        int i = log2[u ^ v];
        product = product * fromTo[i][c];
        u = v;
      }
      curr = curr - product;
    }
    connectedProb[m] = curr;
  }
  int m = mask - 1;
  num ans = num(0);
  for (int s = m; s; s = (s - 1) & m) {
    num product = connectedProb[s];
    int c = m ^ s;
    int u = s;
    int count = 0;
    while (u) {
      count++;
      int v = u & (u - 1);
      int i = log2[u ^ v];
      product = product * fromTo[i][c];
      u = v;
    }
    product = product * count;
    ans = ans + product;
  }
  cout << ans << '\n';
}

```