Marek and Matching (hard version)
Contest: Dasha Code Championship - SPb Finals Round (only for onsite-finalists)
Difficulty rating: 3200
Tags: brute force, probabilities

This is a harder version of the problem. In this version, $$$n \le 7$$$.

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

Marek chooses an integer $$$n$$$ and $$$n^2$$$ integers $$$p_{ij}$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le n$$$). He then generates a random bipartite graph with $$$2n$$$ vertices. There are $$$n$$$ vertices on the left side: $$$\ell_1, \ell_2, \dots, \ell_n$$$, and $$$n$$$ vertices on the right side: $$$r_1, r_2, \dots, r_n$$$. For each $$$i$$$ and $$$j$$$, he puts an edge between vertices $$$\ell_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 $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{10^9+7}$$$. Let $$$Q^{-1}$$$ be an integer for which $$$Q \cdot Q^{-1} \equiv 1 \pmod{10^9+7}$$$. Print the value of $$$P \cdot Q^{-1}$$$ modulo $$$10^9+7$$$.

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$\mathbf{1 \le n \le 7}$$$). 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}, \dots, p_{in}$$$ ($$$0 \le p_{ij} \le 100$$$); $$$p_{ij}$$$ denotes the probability, in percent, of an edge appearing between $$$\ell_i$$$ and $$$r_j$$$.

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

Constraints:
Time limit: 15.0 s
Memory limit: 256.0 MB

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

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

Example input:
2
50 50
50 50

Example output:
937500007

Example input:
3
3 1 4
1 5 9
2 6 5

Example output:
351284554

Editorial:
Let's consider another approach that can solve the hard subtask as well.
In the algorithm above, we computed all $$$k$$$-element subsets of $$$L$$$, $$$|L|=n$$$, that can match perfectly with some fixed $$$k$$$ vertices on the right. It turns out that not all families of subsets can be generated — for instance, if two sets: $$$\{\ell_1, \ell_2\}$$$ and $$$\{\ell_3, \ell_4\}$$$ can both match perfectly with $$$\{r_1, r_2\}$$$, then one of the following subsets: $$$\{\ell_1, \ell_3\}$$$ and $$$\{\ell_1, \ell_4\}$$$ must match perfectly as well. We'll try to use this observation to solve the problem.
Let's add the vertices of $$$R$$$ one by one. After adding vertices $$$r_1, r_2, \dots, r_k$$$, consider all families of $$$k$$$-element subsets of $$$L$$$ which can match perfectly with $$$\{r_1, r_2, \dots, r_k\}$$$ in any generated graph. Now try adding $$$r_{k+1}$$$. Check all $$$2^n$$$ ways of randomly drawing a subset of $$$n$$$ edges incident to $$$r_{k+1}$$$. For each such subset and for each family $$$\mathcal{F}_k$$$ of $$$k$$$-element subsets computed previously, we need to compute the new family $$$\mathcal{F}_{k+1}$$$ of $$$(k+1)$$$-element subsets of $$$L$$$ matching perfectly with $$$\{r_1, r_2, \dots, r_{k+1}\}$$$. We can do it in a straightforward way — iterate over all $$$(k+1)$$$-element subsets $$$S \subseteq L$$$. If $$$S$$$ matches perfectly with $$$k+1$$$ vertices on the right, then $$$r_{k+1}$$$ must be connected to some vertex $$$\ell \in S$$$, and $$$\{r_1, \dots, r_k\}$$$ must match perfectly with $$$S \setminus \{\ell\}$$$.
This allows us to solve the whole problem in $$$O(n \cdot \text{max number of families at any moment} \cdot 2^n)$$$ time. It turns out that for $$$n=7$$$, here are at most $$$\sim 30\,000$$$ families for any value of $$$k$$$. This allows to solve the problem in a reasonable time. The model solution finishes within $$$1.5$$$ seconds, but some breathing space was added so that some less efficient implementations will pass as well.