Problem: The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.

Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.

Input

The first line contains a single integer n (1 ≤ n ≤ 18) — the number of participants of the Sith Tournament.

Each of the next n lines contains n real numbers, which form a matrix pij (0 ≤ pij ≤ 1). Each its element pij is the probability that the i-th participant defeats the j-th in a duel.

The elements on the main diagonal pii are equal to zero. For all different i, j the equality pij + pji = 1 holds. All probabilities are given with no more than six decimal places.

Jedi Ivan is the number 1 in the list of the participants.

Output

Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10 - 6.

Examples

Input

3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0


Output

0.680000000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T SQR(T x) {
  return x * x;
}
template <typename T>
inline T MIN(T x, T y) {
  return (x < y) ? x : y;
}
template <typename T>
inline T MAX(T x, T y) {
  return (x > y) ? x : y;
}
template <typename T>
inline T ABS(T x) {
  return (x > 0) ? x : -x;
}
template <typename T>
inline void UPDATE_MIN(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <typename T>
inline void UPDATE_MAX(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <typename T>
inline int ARGMAX(T cont) {
  return max_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int ARGMIN(T cont) {
  return min_element(cont.begin(), cont.end()) - cont.begin();
}
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (__typeof(n - 1) i = (0), __tmpvar__end87 = (n - 1); i < __tmpvar__end87;
       i++)
    s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <class T>
inline string TOSTR(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
inline void PR(void) {}
inline void PR(int x) { printf("%d", x); }
inline void PR(long long x) { printf("%lld", x); }
inline void PR(char *s) { printf("%s", s); }
inline void PR(const char *s) { printf("%s", s); }
inline void PR(double f) { printf("%.10lf", f); }
inline void PR(long double f) { printf("%.10llf", f); }
inline void PR(vector<int> &vec) {
  for (auto x : vec) {
    PR(x);
    putc(0x20, stdout);
  }
}
template <typename T>
inline void PRS(T x) {
  PR(x);
  putc(0x20, stdout);
}
template <typename T>
inline void PRN(T x) {
  PR(x);
  putc(0x0a, stdout);
}
void PRN(void) { putc(0x0a, stdout); }
inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
inline long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
inline long long powmod(long long a, long long p, long long m) {
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
struct pairhash {
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};
template <typename K, typename V>
V GetWithDef(const std::map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
template <typename K, typename V>
V GetWithDef(const std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  return (it == m.end()) ? defval : it->second;
}
template <typename K, typename V>
void SetDef(std::unordered_map<K, V> &m, const K &key, const V &defval) {
  auto it = m.find(key);
  if (it == m.end()) m[key] = defval;
}
const int MOD = 1000 * 1000 * 1000 + 7;
const double PI = 3.1415926535897932384626433832795l;
inline void addto(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void subto(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void multo(int &a, int b) { a = (long long)a * b % MOD; }
inline int mul(int a, int b) { return (long long)a * b % MOD; }
inline int mulmod(int a, int b, int mod) { return (long long)a * b % mod; }
inline int powmod(int a, int e, int mod) {
  int x;
  for (x = 1; e > 0; e >>= 1) {
    if (e & 1) x = mulmod(x, a, mod);
    a = mulmod(a, a, mod);
  }
  return x;
}
inline int invmod_prime(int a, int mod) { return powmod(a, mod - 2, mod); }
inline long long invmod_LL(long long p) {
  long long q = p;
  for (long long a = p * p; a != 1; a *= a) q *= a;
  return q;
}
int N, M, K, L, E, Q;
double pwin[100][100];
bool visited[1 << 18] = {};
double cache[1 << 18] = {};
double solve(int mask) {
  if (!(mask & 1)) return 0.0;
  if (mask == 1) return 1.0;
  if (!visited[mask]) {
    double res = 0;
    for (__typeof(N) i = (0), __tmpvar__end250 = (N); i < __tmpvar__end250;
         i++) {
      if (!(mask & (1 << i))) continue;
      for (__typeof(N) j = (1), __tmpvar__end252 = (N); j < __tmpvar__end252;
           j++) {
        if (i == j) continue;
        if (!(mask & (1 << j))) continue;
        int mask1 = mask ^ (1 << i);
        double prob1 = pwin[j][i];
        int mask2 = mask ^ (1 << j);
        double prob2 = pwin[i][j];
        UPDATE_MAX(res, prob1 * solve(mask1) + prob2 * solve(mask2));
      }
    }
    cache[mask] = res;
    visited[mask] = 1;
  }
  return cache[mask];
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &N);
  for (__typeof(N) i = (0), __tmpvar__end270 = (N); i < __tmpvar__end270; i++) {
    for (__typeof(N) j = (0), __tmpvar__end271 = (N); j < __tmpvar__end271;
         j++) {
      scanf("%lf", &pwin[i][j]);
      1;
    }
  }
  int mask = (1 << N) - 1;
  double ans = solve(mask);
  PRN(ans);
  return 0;
}