Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Bingo

time limit per test

7 secondsmemory limit per test

512 megabytesinput

standard inputoutput

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

Input

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

Output

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

Examples

Input

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

Note

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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/04/2022 04:27:13 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|