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

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