Problem: This is an easier version of the problem. In this version, n ≤ 6.

Marek is working hard on creating strong testcases to his new algorithmic problem. You want to know what it is? Nah, we're not telling you. However, we can tell you how he generates the testcases.

Marek chooses an integer n and n^2 integers p_{ij} (1 ≤ i ≤ n, 1 ≤ j ≤ n). He then generates a random bipartite graph with 2n vertices. There are n vertices on the left side: ℓ_1, ℓ_2, ..., ℓ_n, and n vertices on the right side: r_1, r_2, ..., r_n. For each i and j, he puts an edge between vertices ℓ_i and r_j with probability p_{ij} percent.

It turns out that the tests will be strong only if a perfect matching exists in the generated graph. What is the probability that this will occur?

It can be shown that this value can be represented as P/Q where P and Q are coprime integers and Q not≡ 0 \pmod{10^9+7}. Let Q^{-1} be an integer for which Q ⋅ Q^{-1} ≡ 1 \pmod{10^9+7}. Print the value of P ⋅ Q^{-1} modulo 10^9+7.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 6). The following n lines describe the probabilities of each edge appearing in the graph. The i-th of the lines contains n integers p_{i1}, p_{i2}, ..., p_{in} (0 ≤ p_{ij} ≤ 100); p_{ij} denotes the probability, in percent, of an edge appearing between ℓ_i and r_j.

Output

Print a single integer — the probability that the perfect matching exists in the bipartite graph, written as P ⋅ Q^{-1} \pmod{10^9+7} for P, Q defined above.

Examples

Input


2
50 50
50 50


Output


937500007


Input


3
3 1 4
1 5 9
2 6 5


Output


351284554

Note

In the first sample test, each of the 16 graphs below is equally probable. Out of these, 7 have a perfect matching:

<image>

Therefore, the probability is equal to 7/16. As 16 ⋅ 562 500 004 = 1 \pmod{10^9+7}, the answer to the testcase is 7 ⋅ 562 500 004 mod{(10^9+7)} = 937 500 007.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
struct mod_int {
  int val;
  mod_int(long long v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int mod_inv(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  mod_int &operator+=(const mod_int &other) {
    val += other.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  mod_int &operator-=(const mod_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  mod_int &operator*=(const mod_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  mod_int &operator/=(const mod_int &other) { return *this *= other.inv(); }
  friend mod_int operator+(const mod_int &a, const mod_int &b) {
    return mod_int(a) += b;
  }
  friend mod_int operator-(const mod_int &a, const mod_int &b) {
    return mod_int(a) -= b;
  }
  friend mod_int operator*(const mod_int &a, const mod_int &b) {
    return mod_int(a) *= b;
  }
  friend mod_int operator/(const mod_int &a, const mod_int &b) {
    return mod_int(a) /= b;
  }
  mod_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  mod_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  mod_int operator++(int) {
    mod_int before = *this;
    ++*this;
    return before;
  }
  mod_int operator--(int) {
    mod_int before = *this;
    --*this;
    return before;
  }
  mod_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const mod_int &other) const { return val == other.val; }
  bool operator!=(const mod_int &other) const { return val != other.val; }
  mod_int inv() const { return mod_inv(val); }
  mod_int pow(long long p) const {
    assert(p >= 0);
    mod_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
};
const int N_MAX = 7;
int N;
mod_int probability[N_MAX][N_MAX];
int main() {
  cin >> N;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      int p;
      cin >> p;
      probability[i][j] = mod_int(p) / mod_int(100);
    }
  vector<vector<int>> masks_with_count(N_MAX + 1);
  vector<int> lookup(1 << N, -1);
  for (int mask = 0; mask < 1 << N; mask++) {
    int count = __builtin_popcount(mask);
    lookup[mask] = masks_with_count[count].size();
    masks_with_count[count].push_back(mask);
  }
  map<long long, mod_int> possible_masks;
  possible_masks[1 << lookup[0]] = 1;
  for (int left = 0; left < N; left++) {
    map<long long, mod_int> new_possible_masks;
    vector<mod_int> products(1 << N, 1);
    for (int current = 0; current < 1 << N; current++)
      for (int right = 0; right < N; right++)
        products[current] *= (current >> right & 1)
                                 ? probability[left][right]
                                 : 1 - probability[left][right];
    for (auto &p : possible_masks) {
      long long possible = p.first;
      mod_int prob = p.second;
      vector<long long> new_bits(N, 0);
      for (int mask : masks_with_count[left])
        if (possible >> lookup[mask] & 1)
          for (int i = 0; i < N; i++)
            if ((mask >> i & 1) == 0)
              new_bits[i] |= 1LL << lookup[mask | 1 << i];
      for (int current = 0; current < 1 << N; current++) {
        long long new_possible = 0;
        for (int prefix = current; prefix != 0; prefix &= prefix - 1)
          new_possible |= new_bits[__builtin_ctz(prefix)];
        new_possible_masks[new_possible] += prob * products[current];
      }
    }
    possible_masks = new_possible_masks;
    cerr << possible_masks.size() << endl;
  }
  mod_int answer = 0;
  for (auto &p : possible_masks)
    if (p.first >> lookup[(1 << N) - 1] & 1) answer += p.second;
  cout << (int)answer << '\n';
}