# Bingo solution codeforces – Getting ready for VK Fest 2021, you prepared a table with nn rows and nn columns

## Bingo solution codeforces

Getting ready for VK Fest 2021, you prepared a table with nn rows and nn 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 ii and column jj will happen with probability ai,j104ai,j⋅10−4. All of the events are mutually independent.

Let’s call the table winning if there exists a line such that all nn events on it happen. The line could be any horizontal line (cells (i,1),(i,2),,(i,n)(i,1),(i,2),…,(i,n) for some ii), any vertical line (cells (1,j),(2,j),,(n,j)(1,j),(2,j),…,(n,j) for some jj), the main diagonal (cells (1,1),(2,2),,(n,n)(1,1),(2,2),…,(n,n)), or the antidiagonal (cells (1,n),(2,n1),,(n,1)(1,n),(2,n−1),…,(n,1)).

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

Input Bingo solution codeforces

The first line contains a single integer nn (2n212≤n≤21) — the dimensions of the table.

The ii-th of the next nn lines contains nn integers ai,1,ai,2,,ai,nai,1,ai,2,…,ai,n (0<ai,j<1040<ai,j<104). The probability of event in cell (i,j)(i,j) to happen is ai,j104ai,j⋅10−4.

Output  Bingo solution codeforces

Print the probability that your table will be winning, modulo 3160731607.

Formally, let M=31607M=31607. It can be shown that the answer can be expressed as an irreducible fraction pqpq, where pp and qq are integers and q≢0(modM)q≢0(modM). Output the integer equal to pq1modMp⋅q−1modM. In other words, output such an integer xx that 0x<M0≤x<M and xqp(modM)x⋅q≡p(modM).

Examples Bingo solution codeforces
input Bingo solution codeforces

Copy
2
5000 5000
5000 5000

output

Copy
5927

input

Copy
2
2500 6000
3000 4000

output

Copy
24812

input

Copy
3
1000 2000 3000
4000 5000 6000
7000 8000 9000

output

Copy
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 11161116, and 59271611(mod31607)5927⋅16≡11(mod31607).