A14324. 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).

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 < a_{i, j} < 10^4$ ). The probability of event in cell $(i, j)$ to happen is $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 < M$ and $x \cdot q \equiv p \pmod{M}$ .

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}$ .