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

This is an easier version of the problem. In this version, $$$n \le 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 \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 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}, \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: 7.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 first discuss one of possible solutions for the easy subtask.
Let's assume that $$$n=6$$$ (all smaller $$$n$$$'s can be easily reduced to this case). There are two layers of vertices: left $$$L = \{\ell_1, \ell_2, \dots, \ell_6\}$$$ and right $$$R = \{r_1, r_2, \dots, r_6\}$$$. Let's do meet-in-the-middle on the right layer: $$$R_a = \{r_1, r_2, r_3\}$$$ and $$$R_b = \{r_4, r_5, r_6\}$$$.
Consider two parts of the graph: between $$$L$$$ and $$$R_a$$$, and between $$$L$$$ and $$$R_b$$$. Each of them has $$$n \cdot \frac{n}{2} = 18$$$ edges, so we can try all subsets of edges in each of them separately. For each such subset:
• Compute the probability that we'll generate exactly this subset of edges.
• Find all $$$3$$$-element subsets of $$$L$$$ which can match perfectly with the currently considered half of $$$R$$$.
This can be done easily in $$$2^{18} \times \mathrm{poly}(n)$$$ time.
Now, here's a trick — there are only $$${6 \choose 3} = 20$$$ three-element subsets of $$$L$$$! Therefore, for each $$$20$$$-element mask $$$M$$$, we can find:
• $$$p_a(M)$$$ — the probability that the set of three-element subsets of $$$L$$$ matching perfectly with $$$R_a$$$ is exactly $$$M$$$,
• $$$p_b(M)$$$ — the probability that the set of three-element subsets of $$$L$$$ whose complements match perfectly with $$$R_b$$$ is exactly $$$M$$$.
Let's find the probability that there is no perfect matching in the graph. We can see that it's $$$\sum_{A \cap B = \varnothing} p_a(A) p_b(B)$$$ where $$$A$$$ and $$$B$$$ are $$$20$$$-element masks. This can be solved easily using SOS dynamic programming technique. If we let $$$q_b(X) := \sum_{Y \subseteq X} p_b(X)$$$, then the required sum is $$$\sum_{A \subseteq [20]} p_a(A) q_b([20] \setminus A)$$$ where $$$[20] = \{1,2,3,\dots,20\}$$$.
Therefore, this algorithm allows us to solve the easy version of the problem in $$$2^{18} \cdot \mathrm{poly}(n) + 2^{20} \cdot 20$$$ time.