#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  os << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", ");
  }
  os << "}";
  return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U> pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
  os << "{";
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << "(" << itr->first << ", " << itr->second << ")";
    itr++;
    if (itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
  os << "{";
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << (*itr);
    ++itr;
    if (itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
int scan() { return getchar(); }
void scan(int& a) { cin >> a; }
void scan(long long& a) { cin >> a; }
void scan(char& a) { cin >> a; }
void scan(double& a) { cin >> a; }
void scan(string& a) { cin >> a; }
template <class T, class S>
void scan(pair<T, S>& p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T>&);
template <class T>
void scan(vector<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(T& a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
  scan(head);
  IN(tail...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
  std::fill((T*)array, (T*)(array + N), val);
}
template <class T>
T ceil(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T>
T floor(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? x / y : (x + y - 1) / y);
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota((a).begin(), (a).end(), 0);
  return a;
}
template <class T>
T POW(T x, int n) {
  T res = 1;
  for (; n; n >>= 1, x *= x) {
    if (n & 1) res *= x;
  }
  return res;
}
long long pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
long long allbit(long long n) { return (1LL << n) - 1; }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
template <class S>
void fold_in(vector<S>& v) {}
template <typename Head, typename... Tail, class S>
void fold_in(vector<S>& v, Head&& a, Tail&&... tail) {
  for (auto e : a) v.emplace_back(e);
  fold_in(v, tail...);
}
template <class S>
void renumber(vector<S>& v) {}
template <typename Head, typename... Tail, class S>
void renumber(vector<S>& v, Head&& a, Tail&&... tail) {
  for (auto&& e : a)
    e = distance((v).begin(), lower_bound((v).begin(), (v).end(), (e)));
  renumber(v, tail...);
}
template <class S, class... Args>
void zip(vector<S>& head, Args&&... args) {
  vector<S> v;
  fold_in(v, head, args...);
  sort((v).begin(), (v).end()),
      v.erase(unique((v).begin(), (v).end()), v.end());
  renumber(v, head, args...);
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <unsigned int mod>
class ModInt {
 private:
  unsigned int v;
  static unsigned int norm(const unsigned int& x) {
    return x < mod ? x : x - mod;
  }
  static ModInt make(const unsigned int& x) {
    ModInt m;
    return m.v = x, m;
  }
  static ModInt inv(const ModInt& x) { return make(inverse(x.v, mod)); }
  static unsigned int inverse(int a, int m) {
    int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;
    while (*v) {
      t = *u / *v;
      swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]),
          swap(u[2] -= t * v[2], v[2]);
    }
    return (u[1] % m + m) % m;
  }

 public:
  ModInt() : v{0} {}
  ModInt(const long long val) : v{norm(val % mod + mod)} {}
  ModInt(const ModInt<mod>& n) : v{n()} {}
  explicit operator bool() const noexcept { return v != 0; }
  bool operator!() const noexcept { return !static_cast<bool>(*this); }
  ModInt& operator=(const ModInt& n) { return v = n(), (*this); }
  ModInt& operator=(const long long val) {
    return v = norm(val % mod + mod), (*this);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); }
  ModInt operator+(const ModInt& val) const { return make(norm(v + val())); }
  ModInt operator-(const ModInt& val) const {
    return make(norm(v + mod - val()));
  }
  ModInt operator*(const ModInt& val) const {
    return make((long long)v * val() % mod);
  }
  ModInt operator/(const ModInt& val) const { return *this * inv(val); }
  ModInt& operator+=(const ModInt& val) { return *this = *this + val; }
  ModInt& operator-=(const ModInt& val) { return *this = *this - val; }
  ModInt& operator*=(const ModInt& val) { return *this = *this * val; }
  ModInt& operator/=(const ModInt& val) { return *this = *this / val; }
  ModInt operator+(const long long val) const { return ModInt{v + val}; }
  ModInt operator-(const long long val) const { return ModInt{v - val}; }
  ModInt operator*(const long long val) const {
    return ModInt{(long long)v * (val % mod)};
  }
  ModInt operator/(const long long val) const {
    return ModInt{(long long)v * inv(val)};
  }
  ModInt& operator+=(const long long val) { return *this = *this + val; }
  ModInt& operator-=(const long long val) { return *this = *this - val; }
  ModInt& operator*=(const long long val) { return *this = *this * val; }
  ModInt& operator/=(const long long val) { return *this = *this / val; }
  bool operator==(const ModInt& val) const { return v == val.v; }
  bool operator!=(const ModInt& val) const { return !(*this == val); }
  bool operator==(const long long val) const {
    return v == norm(val % mod + mod);
  }
  bool operator!=(const long long val) const { return !(*this == val); }
  unsigned int operator()() const { return v; }
  friend ModInt operator+(const long long val, const ModInt& n) {
    return n + val;
  }
  friend ModInt operator-(const long long val, const ModInt& n) {
    return ModInt{val - n()};
  }
  friend ModInt operator*(const long long val, const ModInt& n) {
    return n * val;
  }
  friend ModInt operator/(const long long val, const ModInt& n) {
    return ModInt{val} / n;
  }
  friend bool operator==(const long long val, const ModInt& n) {
    return n == val;
  }
  friend bool operator!=(const long long val, const ModInt& n) {
    return !(val == n);
  }
  friend istream& operator>>(istream& is, ModInt& n) {
    unsigned int v;
    return is >> v, n = v, is;
  }
  friend ostream& operator<<(ostream& os, const ModInt& n) {
    return (os << n());
  }
  friend ModInt mod_pow(ModInt x, long long n) {
    ModInt ans = 1;
    while (n) {
      if (n & 1) ans *= x;
      x *= x, n >>= 1;
    }
    return ans;
  }
};
using mod = ModInt<1000000007>;
mod inv[200000], fac[200000], finv[200000];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < 200000; i++) {
    inv[i] = 1000000007 - inv[1000000007 % i] * (1000000007 / i);
    fac[i] = fac[i - 1] * i;
    finv[i] = finv[i - 1] * inv[i];
  }
}
mod comb(int a, int b) {
  if (a < b) return 0;
  return fac[a] * finv[b] * finv[a - b];
}
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator;
template <class _Key, class _Tp, class _Hash = hash<_Key>,
          bool DOWNSIZE = false>
class UnorderedMap {
 private:
  using iterator = UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  using value_type = _Tp;
  using data_type = pair<_Key, _Tp>;
  using aligned_pointer =
      typename aligned_storage<sizeof(value_type), alignof(value_type)>::type;
  friend UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  struct bucket {
    _Key _key;
    short int _dist;
    bool _last, _end;
    aligned_pointer _value_ptr;
    bucket() noexcept : _dist(-1), _last(false), _end(false) {}
    bucket& operator=(const bucket& another) noexcept {
      _key = another._key, _dist = another._dist, _last = another._last,
      _end = another._end;
      if (!another.empty()) {
        new (&_value_ptr) value_type(
            *reinterpret_cast<const value_type*>(&another._value_ptr));
      }
      return *this;
    }
    ~bucket() {
      if (!empty()) _delete();
    }
    inline void clear() noexcept { _dist = -1; }
    inline void _delete() { _dist = -1, value_ptr()->~value_type(); }
    inline bool empty() const noexcept { return (_dist == -1); }
    inline value_type& value() noexcept {
      return *reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline value_type* value_ptr() noexcept {
      return reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline void new_value(value_type&& value) {
      new (&_value_ptr) value_type(move(value));
    }
  };
  inline static unsigned int ceilpow2(unsigned int u) noexcept {
    if (u == 0u) return 0u;
    --u, u |= u >> 1, u |= u >> 2, u |= u >> 4, u |= u >> 8;
    return (u | (u >> 16)) + 1u;
  }
  inline static bucket* increment(bucket* cur) noexcept {
    for (++cur; !cur->_end; ++cur) {
      if (!cur->empty()) break;
    }
    return cur;
  }
  inline bucket* next_bucket(bucket* cur) const noexcept {
    return cur->_last ? _buckets : cur + 1;
  }
  inline unsigned int make_hash(const _Key& key) const noexcept {
    return _Hash()(key);
  }
  inline float load_rate() const noexcept {
    return (float)_data_count / _bucket_count;
  }
  bucket* insert(bucket* cur, _Key&& key, short int dist, value_type&& value) {
    bucket* ret = cur;
    bool flag = false;
    while (true) {
      if (cur->empty()) {
        cur->_key = move(key), cur->_dist = dist, cur->new_value(move(value));
        if (!flag) ret = cur, flag = true;
        break;
      } else if (dist > cur->_dist) {
        swap(key, cur->_key), swap(dist, cur->_dist), swap(value, cur->value());
        if (!flag) ret = cur, flag = true;
      }
      ++dist;
      cur = next_bucket(cur);
    }
    return ret;
  }
  template <class Key>
  bucket* _find(Key&& key, bool push = false) {
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    if (!push) return _buckets + _bucket_count;
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    value_type new_value = value_type();
    _Key new_key = forward<Key>(key);
    return insert(cur, move(new_key), dist, move(new_value));
  }
  template <class Data>
  bucket* find_insert(Data&& data) {
    const _Key& key = data.first;
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    data_type new_data = forward<Data>(data);
    return insert(cur, move(new_data.first), dist, move(new_data.second));
  }
  template <typename... Args>
  bucket* emplace(Args&&... args) {
    return find_insert(data_type(forward<Args>(args)...));
  }
  bucket* backward_shift(bucket* cur, bool next_ret) {
    bucket *next = next_bucket(cur), *ret = cur;
    if (next->_dist < 1) return next_ret ? increment(cur) : cur;
    do {
      cur->_key = next->_key, cur->_dist = next->_dist - 1;
      cur->new_value(move(next->value()));
      cur = next, next = next_bucket(cur);
    } while (next->_dist >= 1);
    cur->clear();
    return ret;
  }
  bucket* erase_impl(bucket* cur, bool next_ret) {
    assert(static_cast<size_t>(cur - _buckets) != _bucket_count);
    cur->_delete();
    --_data_count;
    return backward_shift(cur, next_ret);
  }
  bucket* erase_itr(bucket* cur, bool next_ret = true) {
    const _Key key = cur->_key;
    return erase_impl(rehash_check() ? _find(key) : cur, next_ret);
  }
  size_t erase_key(const _Key& key) {
    rehash_check();
    bucket* cur = _find(key);
    if (static_cast<size_t>(cur - _buckets) == _bucket_count) {
      return 0;
    } else {
      erase_impl(_find(key), false);
      return 1;
    }
  }
  bool rehash_check() {
    if (_bucket_count == 0) {
      rehash(1u);
      return true;
    } else if (load_rate() >= MAX_LOAD_RATE) {
      rehash(_bucket_count * 2u);
      return true;
    } else if (DOWNSIZE) {
      if (load_rate() <= MIN_LOAD_RATE && _bucket_count >= DOWNSIZE_THRESHOLD) {
        rehash(_bucket_count / 2u);
        return true;
      }
    }
    return false;
  }
  void move_data(bucket* cur) {
    insert(_buckets + (make_hash(cur->_key) & _mask), move(cur->_key), 0,
           move(cur->value()));
  }
  void rehash(unsigned int new_bucket_count) {
    UnorderedMap new_unordered_map(new_bucket_count);
    new_unordered_map._data_count = _data_count;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      if (!cur->empty()) {
        new_unordered_map.move_data(cur);
      }
    }
    swap(*this, new_unordered_map);
  }
  friend void swap(UnorderedMap& ump1, UnorderedMap& ump2) {
    swap(ump1._bucket_count, ump2._bucket_count);
    swap(ump1._mask, ump2._mask);
    swap(ump1._data_count, ump2._data_count);
    swap(ump1._buckets, ump2._buckets);
  }

 private:
  unsigned int _bucket_count, _mask, _data_count;
  bucket* _buckets;

 public:
  const float MAX_LOAD_RATE = 0.5f;
  const float MIN_LOAD_RATE = 0.1f;
  const unsigned int DOWNSIZE_THRESHOLD = 16u;
  UnorderedMap(unsigned int bucket_size = 0u)
      : _bucket_count(ceilpow2(bucket_size)),
        _mask(_bucket_count - 1),
        _data_count(0u),
        _buckets(new bucket[_bucket_count + 1]) {
    if (_bucket_count > 0)
      _buckets[_bucket_count - 1]._last = true;
    else
      _mask = 0;
    _buckets[_bucket_count]._end = true;
  }
  UnorderedMap(const UnorderedMap& another)
      : _bucket_count(another._bucket_count),
        _mask(another._mask),
        _data_count(another._data_count) {
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
  }
  UnorderedMap(UnorderedMap&& another)
      : _bucket_count(move(another._bucket_count)),
        _mask(move(another._mask)),
        _data_count(move(another._data_count)),
        _buckets(another._buckets) {
    another._buckets = nullptr;
  }
  UnorderedMap& operator=(const UnorderedMap& another) {
    delete[] _buckets;
    _bucket_count = another._bucket_count;
    _mask = another._mask;
    _data_count = another._data_count;
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
    return *this;
  }
  UnorderedMap& operator=(UnorderedMap&& another) {
    delete[] _buckets;
    _bucket_count = move(another._bucket_count);
    _mask = move(another._mask);
    _data_count = move(another._data_count);
    _buckets = another._buckets;
    another._buckets = nullptr;
    return *this;
  }
  void allocate(unsigned int element_size) {
    rehash(ceilpow2(ceil(element_size / MAX_LOAD_RATE) + 1));
  }
  ~UnorderedMap() { delete[] _buckets; }
  friend ostream& operator<<(ostream& os, UnorderedMap& ump) noexcept {
    for (auto val : ump) os << '{' << val.first << ',' << val.second << "} ";
    return os;
  }
  _Tp& operator[](const _Key& key) { return _find(key, true)->value(); }
  _Tp& operator[](_Key&& key) { return _find(move(key), true)->value(); }
  const _Tp& at(const _Key& key) {
    bucket* res = _find(key);
    if (res == _buckets + _bucket_count)
      __throw_out_of_range("Unordered_Map::at");
    return res->value();
  }
  void clear() {
    UnorderedMap new_unordered_map(0u);
    swap(*this, new_unordered_map);
  }
  size_t size() const noexcept { return _data_count; }
  size_t bucket_count() const noexcept { return _bucket_count; }
  bool empty() const noexcept { return (_data_count == 0); }
  iterator begin() noexcept {
    return (_buckets->empty() && _bucket_count > 0)
               ? iterator(increment(_buckets))
               : iterator(_buckets);
  }
  iterator end() noexcept { return iterator(_buckets + _bucket_count); }
  iterator find(const _Key& key) { return iterator(_find(key)); }
  iterator insert(const data_type& data) { return iterator(find_insert(data)); }
  iterator insert(data_type&& data) {
    return iterator(find_insert(move(data)));
  }
  template <typename... Args>
  iterator emplace(Args&&... args) {
    return iterator(_emplace(forward<Args>(args)...));
  }
  size_t erase(const _Key& key) { return erase_key(key); }
  iterator erase(const iterator& itr) {
    return iterator(erase_itr(itr.bucket_ptr));
  }
  void simple_erase(const _Key& key) { erase_key(key); }
  void simple_erase(const iterator& itr) { erase_itr(itr.bucket_ptr, false); }
  short int maximum_distance() const noexcept {
    short int ret = -1;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      ret = max(ret, cur->_dist);
    }
    return ret;
  }
};
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator {
 private:
  friend UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>;
  typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket* bucket_ptr;
  using iterator_category = forward_iterator_tag;
  using value_type = pair<const _Key, _Tp>;
  using difference_type = ptrdiff_t;
  using reference = pair<const _Key&, _Tp&>;

 private:
  UnorderedMapIterator(
      typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket*
          _bucket_ptr) noexcept
      : bucket_ptr(_bucket_ptr) {}

 public:
  UnorderedMapIterator() noexcept : bucket_ptr() {}
  UnorderedMapIterator(const UnorderedMapIterator& itr) noexcept
      : bucket_ptr(itr.bucket_ptr) {}
  UnorderedMapIterator& operator=(const UnorderedMapIterator& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  UnorderedMapIterator& operator=(const UnorderedMapIterator&& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  reference operator*() const noexcept {
    return {bucket_ptr->_key, bucket_ptr->value()};
  }
  UnorderedMapIterator& operator++() noexcept {
    return bucket_ptr =
               UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(bucket_ptr),
           *this;
  }
  UnorderedMapIterator operator++(int) const noexcept {
    return UnorderedMapIterator(
        UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(this->bucket_ptr));
  }
  bool operator==(const UnorderedMapIterator& itr) const noexcept {
    return !(*this != itr);
  };
  bool operator!=(const UnorderedMapIterator& itr) const noexcept {
    return bucket_ptr != itr.bucket_ptr;
  }
};
mod p[15][15];
mod dp[1 << 14];
UnorderedMap<int, mod> mp[1 << 14];
int main() {
  int n;
  IN(n);
  vector<mod> a(n);
  IN(a);
  for (int i = 0; i < (int)(n); ++i) {
    for (int j = 0; j < (int)(n); ++j) {
      if (i == j) continue;
      p[i][j] = (a[i]) / (a[i] + a[j]);
    }
  }
  for (int bits = 0; bits < (int)(1 << n); ++bits) {
    if (bits == 0) continue;
    int pbits = (allbit(n) ^ bits);
    for (int nxt = 0;; nxt = (nxt - pbits) & pbits) {
      if (nxt == 0) {
        mp[bits][nxt] = 1;
      } else {
        int k = lowbit(nxt);
        mod tmp = 1;
        for (int i = 0; i < (int)(n); ++i) {
          if ((bits >> i) & 1) {
            tmp *= p[i][k];
          }
        }
        mp[bits][nxt] = mp[bits][nxt ^ (1 << k)] * tmp;
      }
      if (nxt == pbits) break;
    }
  }
  mod res = 0;
  for (int i = 0; i < (int)(n); ++i) {
    Fill(dp, 0);
    for (int bits = (int)(1 << i); bits < (int)((1 << n)); ++bits) {
      if ((bits >> i) & 1) {
        dp[bits] = 1;
        for (int nxt = bits;; nxt = (nxt - 1) & bits) {
          if (nxt != bits) {
            if ((nxt >> i) & 1) {
              dp[bits] -= dp[nxt] * mp[bits ^ nxt][nxt];
              (void(0));
            }
          }
          if (!nxt) break;
        }
        (void(0));
      }
    }
    res += dp[allbit(n)];
    (void(0));
  }
  cout << res << endl;
  return 0;
}

### 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>
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  os << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", ");
  }
  os << "}";
  return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U> pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
  os << "{";
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << "(" << itr->first << ", " << itr->second << ")";
    itr++;
    if (itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
  os << "{";
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << (*itr);
    ++itr;
    if (itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
int scan() { return getchar(); }
void scan(int& a) { cin >> a; }
void scan(long long& a) { cin >> a; }
void scan(char& a) { cin >> a; }
void scan(double& a) { cin >> a; }
void scan(string& a) { cin >> a; }
template <class T, class S>
void scan(pair<T, S>& p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T>&);
template <class T>
void scan(vector<T>& a) {
  for (auto& i : a) scan(i);
}
template <class T>
void scan(T& a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head& head, Tail&... tail) {
  scan(head);
  IN(tail...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
  std::fill((T*)array, (T*)(array + N), val);
}
template <class T>
T ceil(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T>
T floor(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? x / y : (x + y - 1) / y);
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota((a).begin(), (a).end(), 0);
  return a;
}
template <class T>
T POW(T x, int n) {
  T res = 1;
  for (; n; n >>= 1, x *= x) {
    if (n & 1) res *= x;
  }
  return res;
}
long long pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
long long allbit(long long n) { return (1LL << n) - 1; }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
template <class S>
void fold_in(vector<S>& v) {}
template <typename Head, typename... Tail, class S>
void fold_in(vector<S>& v, Head&& a, Tail&&... tail) {
  for (auto e : a) v.emplace_back(e);
  fold_in(v, tail...);
}
template <class S>
void renumber(vector<S>& v) {}
template <typename Head, typename... Tail, class S>
void renumber(vector<S>& v, Head&& a, Tail&&... tail) {
  for (auto&& e : a)
    e = distance((v).begin(), lower_bound((v).begin(), (v).end(), (e)));
  renumber(v, tail...);
}
template <class S, class... Args>
void zip(vector<S>& head, Args&&... args) {
  vector<S> v;
  fold_in(v, head, args...);
  sort((v).begin(), (v).end()),
      v.erase(unique((v).begin(), (v).end()), v.end());
  renumber(v, head, args...);
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <unsigned int mod>
class ModInt {
 private:
  unsigned int v;
  static unsigned int norm(const unsigned int& x) {
    return x < mod ? x : x - mod;
  }
  static ModInt make(const unsigned int& x) {
    ModInt m;
    return m.v = x, m;
  }
  static ModInt inv(const ModInt& x) { return make(inverse(x.v, mod)); }
  static unsigned int inverse(int a, int m) {
    int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;
    while (*v) {
      t = *u / *v;
      swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]),
          swap(u[2] -= t * v[2], v[2]);
    }
    return (u[1] % m + m) % m;
  }

 public:
  ModInt() : v{0} {}
  ModInt(const long long val) : v{norm(val % mod + mod)} {}
  ModInt(const ModInt<mod>& n) : v{n()} {}
  explicit operator bool() const noexcept { return v != 0; }
  bool operator!() const noexcept { return !static_cast<bool>(*this); }
  ModInt& operator=(const ModInt& n) { return v = n(), (*this); }
  ModInt& operator=(const long long val) {
    return v = norm(val % mod + mod), (*this);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); }
  ModInt operator+(const ModInt& val) const { return make(norm(v + val())); }
  ModInt operator-(const ModInt& val) const {
    return make(norm(v + mod - val()));
  }
  ModInt operator*(const ModInt& val) const {
    return make((long long)v * val() % mod);
  }
  ModInt operator/(const ModInt& val) const { return *this * inv(val); }
  ModInt& operator+=(const ModInt& val) { return *this = *this + val; }
  ModInt& operator-=(const ModInt& val) { return *this = *this - val; }
  ModInt& operator*=(const ModInt& val) { return *this = *this * val; }
  ModInt& operator/=(const ModInt& val) { return *this = *this / val; }
  ModInt operator+(const long long val) const { return ModInt{v + val}; }
  ModInt operator-(const long long val) const { return ModInt{v - val}; }
  ModInt operator*(const long long val) const {
    return ModInt{(long long)v * (val % mod)};
  }
  ModInt operator/(const long long val) const {
    return ModInt{(long long)v * inv(val)};
  }
  ModInt& operator+=(const long long val) { return *this = *this + val; }
  ModInt& operator-=(const long long val) { return *this = *this - val; }
  ModInt& operator*=(const long long val) { return *this = *this * val; }
  ModInt& operator/=(const long long val) { return *this = *this / val; }
  bool operator==(const ModInt& val) const { return v == val.v; }
  bool operator!=(const ModInt& val) const { return !(*this == val); }
  bool operator==(const long long val) const {
    return v == norm(val % mod + mod);
  }
  bool operator!=(const long long val) const { return !(*this == val); }
  unsigned int operator()() const { return v; }
  friend ModInt operator+(const long long val, const ModInt& n) {
    return n + val;
  }
  friend ModInt operator-(const long long val, const ModInt& n) {
    return ModInt{val - n()};
  }
  friend ModInt operator*(const long long val, const ModInt& n) {
    return n * val;
  }
  friend ModInt operator/(const long long val, const ModInt& n) {
    return ModInt{val} / n;
  }
  friend bool operator==(const long long val, const ModInt& n) {
    return n == val;
  }
  friend bool operator!=(const long long val, const ModInt& n) {
    return !(val == n);
  }
  friend istream& operator>>(istream& is, ModInt& n) {
    unsigned int v;
    return is >> v, n = v, is;
  }
  friend ostream& operator<<(ostream& os, const ModInt& n) {
    return (os << n());
  }
  friend ModInt mod_pow(ModInt x, long long n) {
    ModInt ans = 1;
    while (n) {
      if (n & 1) ans *= x;
      x *= x, n >>= 1;
    }
    return ans;
  }
};
using mod = ModInt<1000000007>;
mod inv[200000], fac[200000], finv[200000];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < 200000; i++) {
    inv[i] = 1000000007 - inv[1000000007 % i] * (1000000007 / i);
    fac[i] = fac[i - 1] * i;
    finv[i] = finv[i - 1] * inv[i];
  }
}
mod comb(int a, int b) {
  if (a < b) return 0;
  return fac[a] * finv[b] * finv[a - b];
}
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator;
template <class _Key, class _Tp, class _Hash = hash<_Key>,
          bool DOWNSIZE = false>
class UnorderedMap {
 private:
  using iterator = UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  using value_type = _Tp;
  using data_type = pair<_Key, _Tp>;
  using aligned_pointer =
      typename aligned_storage<sizeof(value_type), alignof(value_type)>::type;
  friend UnorderedMapIterator<_Key, _Tp, _Hash, DOWNSIZE>;
  struct bucket {
    _Key _key;
    short int _dist;
    bool _last, _end;
    aligned_pointer _value_ptr;
    bucket() noexcept : _dist(-1), _last(false), _end(false) {}
    bucket& operator=(const bucket& another) noexcept {
      _key = another._key, _dist = another._dist, _last = another._last,
      _end = another._end;
      if (!another.empty()) {
        new (&_value_ptr) value_type(
            *reinterpret_cast<const value_type*>(&another._value_ptr));
      }
      return *this;
    }
    ~bucket() {
      if (!empty()) _delete();
    }
    inline void clear() noexcept { _dist = -1; }
    inline void _delete() { _dist = -1, value_ptr()->~value_type(); }
    inline bool empty() const noexcept { return (_dist == -1); }
    inline value_type& value() noexcept {
      return *reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline value_type* value_ptr() noexcept {
      return reinterpret_cast<value_type*>(&_value_ptr);
    }
    inline void new_value(value_type&& value) {
      new (&_value_ptr) value_type(move(value));
    }
  };
  inline static unsigned int ceilpow2(unsigned int u) noexcept {
    if (u == 0u) return 0u;
    --u, u |= u >> 1, u |= u >> 2, u |= u >> 4, u |= u >> 8;
    return (u | (u >> 16)) + 1u;
  }
  inline static bucket* increment(bucket* cur) noexcept {
    for (++cur; !cur->_end; ++cur) {
      if (!cur->empty()) break;
    }
    return cur;
  }
  inline bucket* next_bucket(bucket* cur) const noexcept {
    return cur->_last ? _buckets : cur + 1;
  }
  inline unsigned int make_hash(const _Key& key) const noexcept {
    return _Hash()(key);
  }
  inline float load_rate() const noexcept {
    return (float)_data_count / _bucket_count;
  }
  bucket* insert(bucket* cur, _Key&& key, short int dist, value_type&& value) {
    bucket* ret = cur;
    bool flag = false;
    while (true) {
      if (cur->empty()) {
        cur->_key = move(key), cur->_dist = dist, cur->new_value(move(value));
        if (!flag) ret = cur, flag = true;
        break;
      } else if (dist > cur->_dist) {
        swap(key, cur->_key), swap(dist, cur->_dist), swap(value, cur->value());
        if (!flag) ret = cur, flag = true;
      }
      ++dist;
      cur = next_bucket(cur);
    }
    return ret;
  }
  template <class Key>
  bucket* _find(Key&& key, bool push = false) {
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    if (!push) return _buckets + _bucket_count;
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    value_type new_value = value_type();
    _Key new_key = forward<Key>(key);
    return insert(cur, move(new_key), dist, move(new_value));
  }
  template <class Data>
  bucket* find_insert(Data&& data) {
    const _Key& key = data.first;
    unsigned int hash = make_hash(key);
    bucket* cur = _buckets + (hash & _mask);
    short int dist = 0;
    while (dist <= cur->_dist) {
      if (key == cur->_key) return cur;
      ++dist, cur = next_bucket(cur);
    }
    ++_data_count;
    if (rehash_check()) {
      cur = _buckets + (hash & _mask), dist = 0;
    }
    data_type new_data = forward<Data>(data);
    return insert(cur, move(new_data.first), dist, move(new_data.second));
  }
  template <typename... Args>
  bucket* emplace(Args&&... args) {
    return find_insert(data_type(forward<Args>(args)...));
  }
  bucket* backward_shift(bucket* cur, bool next_ret) {
    bucket *next = next_bucket(cur), *ret = cur;
    if (next->_dist < 1) return next_ret ? increment(cur) : cur;
    do {
      cur->_key = next->_key, cur->_dist = next->_dist - 1;
      cur->new_value(move(next->value()));
      cur = next, next = next_bucket(cur);
    } while (next->_dist >= 1);
    cur->clear();
    return ret;
  }
  bucket* erase_impl(bucket* cur, bool next_ret) {
    assert(static_cast<size_t>(cur - _buckets) != _bucket_count);
    cur->_delete();
    --_data_count;
    return backward_shift(cur, next_ret);
  }
  bucket* erase_itr(bucket* cur, bool next_ret = true) {
    const _Key key = cur->_key;
    return erase_impl(rehash_check() ? _find(key) : cur, next_ret);
  }
  size_t erase_key(const _Key& key) {
    rehash_check();
    bucket* cur = _find(key);
    if (static_cast<size_t>(cur - _buckets) == _bucket_count) {
      return 0;
    } else {
      erase_impl(_find(key), false);
      return 1;
    }
  }
  bool rehash_check() {
    if (_bucket_count == 0) {
      rehash(1u);
      return true;
    } else if (load_rate() >= MAX_LOAD_RATE) {
      rehash(_bucket_count * 2u);
      return true;
    } else if (DOWNSIZE) {
      if (load_rate() <= MIN_LOAD_RATE && _bucket_count >= DOWNSIZE_THRESHOLD) {
        rehash(_bucket_count / 2u);
        return true;
      }
    }
    return false;
  }
  void move_data(bucket* cur) {
    insert(_buckets + (make_hash(cur->_key) & _mask), move(cur->_key), 0,
           move(cur->value()));
  }
  void rehash(unsigned int new_bucket_count) {
    UnorderedMap new_unordered_map(new_bucket_count);
    new_unordered_map._data_count = _data_count;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      if (!cur->empty()) {
        new_unordered_map.move_data(cur);
      }
    }
    swap(*this, new_unordered_map);
  }
  friend void swap(UnorderedMap& ump1, UnorderedMap& ump2) {
    swap(ump1._bucket_count, ump2._bucket_count);
    swap(ump1._mask, ump2._mask);
    swap(ump1._data_count, ump2._data_count);
    swap(ump1._buckets, ump2._buckets);
  }

 private:
  unsigned int _bucket_count, _mask, _data_count;
  bucket* _buckets;

 public:
  const float MAX_LOAD_RATE = 0.5f;
  const float MIN_LOAD_RATE = 0.1f;
  const unsigned int DOWNSIZE_THRESHOLD = 16u;
  UnorderedMap(unsigned int bucket_size = 0u)
      : _bucket_count(ceilpow2(bucket_size)),
        _mask(_bucket_count - 1),
        _data_count(0u),
        _buckets(new bucket[_bucket_count + 1]) {
    if (_bucket_count > 0)
      _buckets[_bucket_count - 1]._last = true;
    else
      _mask = 0;
    _buckets[_bucket_count]._end = true;
  }
  UnorderedMap(const UnorderedMap& another)
      : _bucket_count(another._bucket_count),
        _mask(another._mask),
        _data_count(another._data_count) {
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
  }
  UnorderedMap(UnorderedMap&& another)
      : _bucket_count(move(another._bucket_count)),
        _mask(move(another._mask)),
        _data_count(move(another._data_count)),
        _buckets(another._buckets) {
    another._buckets = nullptr;
  }
  UnorderedMap& operator=(const UnorderedMap& another) {
    delete[] _buckets;
    _bucket_count = another._bucket_count;
    _mask = another._mask;
    _data_count = another._data_count;
    _buckets = new bucket[_bucket_count + 1u];
    for (unsigned int i = 0u; i <= _bucket_count; ++i) {
      _buckets[i] = another._buckets[i];
    }
    return *this;
  }
  UnorderedMap& operator=(UnorderedMap&& another) {
    delete[] _buckets;
    _bucket_count = move(another._bucket_count);
    _mask = move(another._mask);
    _data_count = move(another._data_count);
    _buckets = another._buckets;
    another._buckets = nullptr;
    return *this;
  }
  void allocate(unsigned int element_size) {
    rehash(ceilpow2(ceil(element_size / MAX_LOAD_RATE) + 1));
  }
  ~UnorderedMap() { delete[] _buckets; }
  friend ostream& operator<<(ostream& os, UnorderedMap& ump) noexcept {
    for (auto val : ump) os << '{' << val.first << ',' << val.second << "} ";
    return os;
  }
  _Tp& operator[](const _Key& key) { return _find(key, true)->value(); }
  _Tp& operator[](_Key&& key) { return _find(move(key), true)->value(); }
  const _Tp& at(const _Key& key) {
    bucket* res = _find(key);
    if (res == _buckets + _bucket_count)
      __throw_out_of_range("Unordered_Map::at");
    return res->value();
  }
  void clear() {
    UnorderedMap new_unordered_map(0u);
    swap(*this, new_unordered_map);
  }
  size_t size() const noexcept { return _data_count; }
  size_t bucket_count() const noexcept { return _bucket_count; }
  bool empty() const noexcept { return (_data_count == 0); }
  iterator begin() noexcept {
    return (_buckets->empty() && _bucket_count > 0)
               ? iterator(increment(_buckets))
               : iterator(_buckets);
  }
  iterator end() noexcept { return iterator(_buckets + _bucket_count); }
  iterator find(const _Key& key) { return iterator(_find(key)); }
  iterator insert(const data_type& data) { return iterator(find_insert(data)); }
  iterator insert(data_type&& data) {
    return iterator(find_insert(move(data)));
  }
  template <typename... Args>
  iterator emplace(Args&&... args) {
    return iterator(_emplace(forward<Args>(args)...));
  }
  size_t erase(const _Key& key) { return erase_key(key); }
  iterator erase(const iterator& itr) {
    return iterator(erase_itr(itr.bucket_ptr));
  }
  void simple_erase(const _Key& key) { erase_key(key); }
  void simple_erase(const iterator& itr) { erase_itr(itr.bucket_ptr, false); }
  short int maximum_distance() const noexcept {
    short int ret = -1;
    for (bucket* cur = _buckets; !cur->_end; ++cur) {
      ret = max(ret, cur->_dist);
    }
    return ret;
  }
};
template <class _Key, class _Tp, class _Hash, bool DOWNSIZE>
class UnorderedMapIterator {
 private:
  friend UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>;
  typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket* bucket_ptr;
  using iterator_category = forward_iterator_tag;
  using value_type = pair<const _Key, _Tp>;
  using difference_type = ptrdiff_t;
  using reference = pair<const _Key&, _Tp&>;

 private:
  UnorderedMapIterator(
      typename UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::bucket*
          _bucket_ptr) noexcept
      : bucket_ptr(_bucket_ptr) {}

 public:
  UnorderedMapIterator() noexcept : bucket_ptr() {}
  UnorderedMapIterator(const UnorderedMapIterator& itr) noexcept
      : bucket_ptr(itr.bucket_ptr) {}
  UnorderedMapIterator& operator=(const UnorderedMapIterator& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  UnorderedMapIterator& operator=(const UnorderedMapIterator&& itr) & noexcept {
    return bucket_ptr = itr.bucket_ptr, *this;
  }
  reference operator*() const noexcept {
    return {bucket_ptr->_key, bucket_ptr->value()};
  }
  UnorderedMapIterator& operator++() noexcept {
    return bucket_ptr =
               UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(bucket_ptr),
           *this;
  }
  UnorderedMapIterator operator++(int) const noexcept {
    return UnorderedMapIterator(
        UnorderedMap<_Key, _Tp, _Hash, DOWNSIZE>::increment(this->bucket_ptr));
  }
  bool operator==(const UnorderedMapIterator& itr) const noexcept {
    return !(*this != itr);
  };
  bool operator!=(const UnorderedMapIterator& itr) const noexcept {
    return bucket_ptr != itr.bucket_ptr;
  }
};
mod p[15][15];
mod dp[1 << 14];
UnorderedMap<int, mod> mp[1 << 14];
int main() {
  int n;
  IN(n);
  vector<mod> a(n);
  IN(a);
  for (int i = 0; i < (int)(n); ++i) {
    for (int j = 0; j < (int)(n); ++j) {
      if (i == j) continue;
      p[i][j] = (a[i]) / (a[i] + a[j]);
    }
  }
  for (int bits = 0; bits < (int)(1 << n); ++bits) {
    if (bits == 0) continue;
    int pbits = (allbit(n) ^ bits);
    for (int nxt = 0;; nxt = (nxt - pbits) & pbits) {
      if (nxt == 0) {
        mp[bits][nxt] = 1;
      } else {
        int k = lowbit(nxt);
        mod tmp = 1;
        for (int i = 0; i < (int)(n); ++i) {
          if ((bits >> i) & 1) {
            tmp *= p[i][k];
          }
        }
        mp[bits][nxt] = mp[bits][nxt ^ (1 << k)] * tmp;
      }
      if (nxt == pbits) break;
    }
  }
  mod res = 0;
  for (int i = 0; i < (int)(n); ++i) {
    Fill(dp, 0);
    for (int bits = (int)(1 << i); bits < (int)((1 << n)); ++bits) {
      if ((bits >> i) & 1) {
        dp[bits] = 1;
        for (int nxt = bits;; nxt = (nxt - 1) & bits) {
          if (nxt != bits) {
            if ((nxt >> i) & 1) {
              dp[bits] -= dp[nxt] * mp[bits ^ nxt][nxt];
              (void(0));
            }
          }
          if (!nxt) break;
        }
        (void(0));
      }
    }
    res += dp[allbit(n)];
    (void(0));
  }
  cout << res << endl;
  return 0;
}

```