Davinci’s Demons

★★★★★

0 votes

Easy-Medium

Details

Submissions

Discussion

Editorial

Problem

A brief intro to Davinci's Demons for those who don't know, and a quick recall to those who know :

The show follows Leonardo as he is implicated in the political schemes of the Medici and Pazzi families and their contrasting relationships with the Catholic Church. These events occur alongside Leonardo's quest to obtain the "Book of Leaves" as he finds himself entangled with a cult known as the Sons of Mithras.

When Leonardo Davinci and Girolamo Riario went in search of "Book of Leaves", they found 1 more key which can be split into 2 keys along with the 2 keys which they already had. Totally, they have 4 keys now. When they entered the caves, his mother's voice was audible from one of the caves. To get into that cave he had to solve a riddle -

The riddle had a grid $N*M$ sketched on a stone with holes at some points. On joining particular 4 key holes in the form of a rectangle (with sides parallel to axes of the grid and with positive area), the door of the cave will open. But, for this, the 4 keys had to be inserted in particular cyclic order.

(Assume keys to be $A, B, C, D$ . Then if the correct order of insertion is $DBAC$ , even $BACD$ , $ACDB$ , etc are also correct as they are cyclically equivalent, But $DBCA$ is not equivalent to $DBAC$ or $ACBD$ ).

If they do not insert in a correct cyclic order in particular keyholes they both will die. Davinci, who is genius and confident, is trying to solve the riddle. Girolamo Riario, who is slightly afraid, is trying to calculate the probability that they will die.

Can u help Girolamo to find this probability.!

Note that they will surely die if there are no holes in required format.

Input

2 integers N, M. Followed by N strings in N lines of length M and having 0's and 1's with 0 representing holes.

Output

2 integers P and Q Probability in the form $P/Q$ where P and Q are co-prime to each other.

Constraints

$1 ≤ N, M ≤ 500$ .

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

Here, we can form only 2 rectangles with

$R1$ -> $[(0,1), (0,3), (2, 1), (2, 3)]$ , $R2$ -> $[(1, 0), (1, 2), (3, 0), (3, 2)]$ , where $R1$ and $R2$ are rectangles.

Let’s consider rectangle $R1$ is the correct rectangle. Then following cases arises.

Lets call $(0,1)$ -> $H1, (0,3)$ -> $H2, (2, 1)$ -> $H3, (2, 3)$ -> $H4$ . where $H1, H2, H3, H4$ are the holes.

Lets assume $A, B, C, D$ are the keys. Lets assume proper assignment is $H1$ -> $A, H2$ -> $C, H3$ -> $D, H4$ ->B.

As they are cyclically equivalent you can also insert them in following orders.

$H1$ -> $C, H2$ -> $D, H3$ -> $B, H4$ ->A.

$H1$ -> $D, H2$ -> $B, H3$ -> $A, H4$ ->C.

$H1$ -> $B, H2$ -> $A, H3$ -> $C, H4$ ->D.

We can see that, the probability that he will choose improper rectangle $R2$ and die is $0.5$ . The probability that he will choose improper assignment even if he chooses correct rectangle $R1$ is $(5/6)*(1/2)$ . Hence answer is $5/12 + 1/2 = 11/12$ .