CF1530F Bingo

为了准备 VK Fest 2021，你准备了一个 $n$ 行 $n$ 列的表格，并在每个单元格中填写了与节日相关的某个事件，这些事件可能发生，也可能不发生：例如，你是否会在节日中获奖，或者是否会下雨。 VK 使用的预测算法已经为每个事件是否发生估算了概率。第 $i$ 行第 $j$ 列的事件发生的概率为 $a_{i, j} \cdot 10^{-4}$。所有事件都是相互独立的。 我们称这个表格是“获胜”的，如果存在一条直线，使得该直线上的 $n$ 个事件全部发生。直线可以是任意一行（即第 $i$ 行的 $(i, 1), (i, 2), \ldots, (i, n)$），任意一列（即第 $j$ 列的 $(1, j), (2, j), \ldots, (n, j)$），主对角线（即 $(1, 1), (2, 2), \ldots, (n, n)$），或反对角线（即 $(1, n), (2, n-1), \ldots, (n, 1)$）。 请你计算你的表格成为“获胜”表格的概率，并将结果对 $31\,607$ 取模后输出（见输出格式）。

第一行包含一个整数 $n$（$2 \le n \le 21$）——表格的大小。 接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$（$0 < a_{i, j} < 10^4$）。第 $(i, j)$ 个单元格事件发生的概率为 $a_{i, j} \cdot 10^{-4}$。

输出你的表格成为“获胜”表格的概率，对 $31\,607$ 取模后的结果。 形式化地说，设 $M = 31\,607$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数，且 $q \not\equiv 0 \pmod{M}$。请输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个样例中，任意两个事件都构成一条直线，表格成为“获胜”表格的条件是任意两个事件都发生。其概率为 $\frac{11}{16}$，并且 $5927 \cdot 16 \equiv 11 \pmod{31\,607}$。 由 ChatGPT 4.1 翻译