Bingo solution codeforces
Getting ready for VK Fest 2021, you prepared a table withrows and 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 rowand column will happen with probability . All of the events are mutually independent.
Let’s call the table winning if there exists a line such that all events on it happen. The line could be any horizontal line (cells for some ), any vertical line (cells for some ), the main diagonal (cells ), or the antidiagonal (cells ).
Find the probability of your table to be winning, and output it modulo(see Output section).
The first line contains a single integer( ) — the dimensions of the table.
The-th of the next lines contains integers ( ). The probability of event in cell to happen is .
Print the probability that your table will be winning, modulo.
Formally, let. It can be shown that the answer can be expressed as an irreducible fraction , where and are integers and . Output the integer equal to . In other words, output such an integer that and .
2 5000 5000 5000 5000
2 2500 6000 3000 4000
3 1000 2000 3000 4000 5000 6000 7000 8000 9000
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, and .