CF1210F1.Marek and Matching (easy version)

这是该问题的简化版本。在本版本中，$n \le 6$。

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 6$）。接下来的 $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 翻译