F. Bingotime limit per test7 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputGetting 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).InputThe 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}.OutputPrint 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}.ExamplesInput
2
5000 5000
5000 5000
Output
5927
Input
2
2500 6000
3000 4000
Output
24812
Input
3
1000 2000 3000
4000 5000 6000
7000 8000 9000
Output
25267
NoteIn 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}.
2
5000 5000
5000 5000

5927 
['bitmasks', 'combinatorics', 'dp', 'math', 'probabilities', '*2600']