CF1530F.Bingo

Getting ready for VK Fest 2021, you prepared a table with $n$ rows and $n$ columns, and filled each cell of this table with some event related with the festival that could either happen or not: for example, whether you will win a prize on the festival, or whether it will rain.

Forecasting algorithms used in VK have already estimated the probability for each event to happen. Event in row $i$ and column $j$ will happen with probability $a_{i, j} \cdot 10^{-4}$. All of the events are mutually independent.

Let's call the table winning if there exists a line such that all $n$ events on it happen. The line could be any horizontal line (cells $(i, 1), (i, 2), \ldots, (i, n)$ for some $i$), any vertical line (cells $(1, j), (2, j), \ldots, (n, j)$ for some $j$), the main diagonal (cells $(1, 1), (2, 2), \ldots, (n, n)$), or the antidiagonal (cells $(1, n), (2, n - 1), \ldots, (n, 1)$).

Find the probability of your table to be winning, and output it modulo $31\,607$ (see Output section).

为迎接 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$ 取模后输出（参见“输出”部分）。

The first line contains a single integer $n$ ($2 \le n \le 21$) — the dimensions of the table.

The $i$-th of the next $n$ lines contains $n$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$ ($0 \lt a_{i, j} \lt 10^4$). The probability of event in cell $(i, j)$ to happen is $a_{i, j} \cdot 10^{-4}$.

第一行包含一个整数 $n$（$2 \le n \le 21$）—— 表格的维度。

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

Print the probability that your table will be winning, modulo $31\,607$.

Formally, let $M = 31\,607$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

输出你的桌子获胜的概率，对 $31\,607$ 取模。

形式化地，令 $M = 31\,607$。可以证明，答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first example, any two events form a line, and the table will be winning if any two events happen. The probability of this is $\frac{11}{16}$, and $5927 \cdot 16 \equiv 11 \pmod{31\,607}$.

在第一个例子中，任意两个事件构成一条直线，当任意两个事件发生时，该表格即为获胜状态。该情况发生的概率为 $\frac{11}{16}$，且 $5927 \cdot 16 \equiv 11 \pmod{31\,607}$。