Bytie's Board Game Stationary Probability

Bytie enjoys playing his favorite board game at night. The board has n rows and m columns (so there are n·m cells) and exactly k indistinguishable pieces (with 1 ≤ k ≤ n·m − 1). Each cell is either empty or contains a piece. A move in the game is defined as selecting a cell with a piece and one of its (up, down, left, right) adjacent cells that is empty, and then sliding the piece into that empty cell.

Initially, Bytie places k pieces on the board. Later, he imagines a target configuration (which might be different from the initial one). Every time he makes a move, he first determines all possible moves (over all pieces) and then selects one uniformly at random. For example, if one piece has 1 legal move and another has 2 legal moves, he picks each of the total 3 moves with probability 1/3.

After playing for exactly \[ 100^{100^{100^{100}}} \] moves – an astronomically huge number – the distribution of board configurations converges to the unique stationary distribution of this Markov chain. It can be shown that the stationary probability of any configuration \(s\) is proportional to its number of legal moves, i.e. its degree \(d(s)\). In other words, if \(S\) is the set of configurations reachable from the initial configuration, then the stationary probability of configuration \(s\) is \[ P(s)=\frac{d(s)}{\sum_{t\in S}d(t)}. \]

Your task is: given the board dimensions together with the initial and target configurations, compute the probability that, after the given huge number of moves, the board is in the target configuration. If the target configuration is unreachable from the initial arrangement, the answer is 0. Output the answer as a fraction p/q in its simplest form.

inputFormat

The input is given as follows:

• The first line contains two integers n and m (the number of rows and columns, respectively).
• The next n lines each contain m integers (each 0 or 1) describing the initial board configuration. A 1 indicates that a piece is present, and 0 indicates an empty cell.
• The following n lines each contain m integers (0 or 1) describing the target board configuration. It is guaranteed that both configurations contain the same number of pieces, and 1 ≤ k ≤ n·m − 1.

It is guaranteed that the board is small enough so that the set of reachable states (via the allowed moves) can be enumerated.

outputFormat

Output a single line containing the fraction p/q in its simplest form, which represents the stationary probability of the target configuration after \(100^{100^{100^{100}}}\) moves. If the target configuration is unreachable from the initial configuration, output 0/1.

sample

2 2
1 0
0 0
1 0
0 0

1/4