CF1210F2.Marek and Matching (hard version)

这是该问题的更难版本。在本版本中，$n \le 7$。

Marek 正在努力为他的新算法题目设计强有力的测试数据。你想知道这个题目是什么吗？不，我们不会告诉你。不过，我们可以告诉你他是如何生成测试数据的。

Marek 选择一个整数 $n$ 和 $n^2$ 个整数 $p_{ij}$（$1 \le i \le n$，$1 \le j \le n$）。然后他生成一个有 $2n$ 个点的随机二分图。左侧有 $n$ 个点：$\ell_1, \ell_2, \dots, \ell_n$，右侧有 $n$ 个点：$r_1, r_2, \dots, r_n$。对于每一对 $i$ 和 $j$，他以 $p_{ij}$ 百分比的概率在 $\ell_i$ 和 $r_j$ 之间连一条边。

事实证明，只有当生成的图中存在完美匹配时，测试数据才是强有力的。那么，出现完美匹配的概率是多少？

可以证明，这个概率可以表示为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q \not\equiv 0 \pmod{10^9+7}$。令 $Q^{-1}$ 为满足 $Q \cdot Q^{-1} \equiv 1 \pmod{10^9+7}$ 的整数。请输出 $P \cdot Q^{-1} \bmod 10^9+7$ 的值。

输入的第一行包含一个整数 $n$（$1 \le n \le 7$）。接下来的 $n$ 行描述了每条边出现的概率。第 $i$ 行包含 $n$ 个整数 $p_{i1}, p_{i2}, \dots, p_{in}$（$0 \le p_{ij} \le 100$）；$p_{ij}$ 表示在 $\ell_i$ 和 $r_j$ 之间连边的概率（百分比）。

输出一个整数——该二分图中存在完美匹配的概率，表示为 $P \cdot Q^{-1} \bmod 10^9+7$，其中 $P$、$Q$ 如上所述。

在第一个样例测试中，下面的 $16$ 个图每个出现的概率都相等。其中有 $7$ 个图存在完美匹配：

因此，概率等于 $\frac{7}{16}$。由于 $16 \cdot 562\,500\,004 = 1 \pmod{10^9+7}$，所以本测试点的答案为 $7 \cdot 562\,500\,004 \bmod{(10^9+7)} = 937\,500\,007$。

由 ChatGPT 4.1 翻译