Rhino Tank¶

Indicative time limit: 0.5 seconds (reference environment: environment and measurements)
Actual time limit: twice the reference program's baseline time on the slowest official test file in the target environment, rounded up to a multiple of 0.5 seconds; round up further if the platform requires a coarser unit.
Memory limit: 512 MB

Story¶

The Rhino Tank design team tests each new vehicle using a feature matrix. Features are generated independently, although different positions may use different probability distributions. Every row and every column must contain variation. Compute the probability that a vehicle passes.

Formal Problem Statement¶

Generate an \(n\times n\) matrix whose entries belong to \(\{1,\ldots,m\}\) . For position \((i,j)\) , nonnegative integer weights \(w_{i,j,1},\ldots,w_{i,j,m}\) specify

\[ p_{i,j,c}=\frac{w_{i,j,c}}{\sum_{d=1}^{m}w_{i,j,d}} \]

as the probability of value \(c\) . All positions are independent. A matrix passes if no row has all entries equal and no column has all entries equal. Find its probability of passing.

Let \(P=10^9+7\) . For a probability \(a/b\) , output \(a\cdot b^{-1}\bmod P\) , where \(b^{-1}\) is the multiplicative inverse modulo \(P\) . The bounds ensure every position's weight sum lies between \(1\) and \(P-1\) , so this representation exists.

Input Format¶

The first line contains \(n,m\) . The next \(n^2\) lines describe positions in row-major order, from top to bottom and left to right. Each contains \(m\) integers: the weights for values \(1\) through \(m\) .

Output Format¶

Print the probability of passing, represented modulo \(P\) .

Sample 1¶

Input¶

Output¶

125000001

Explanation¶

Of the \(16\) equally likely matrices, only the two checkerboard patterns pass. Their probability is \(1/8\) , represented by \(125000001\) .

Sample 2¶

Input¶

Output¶

875789148

Explanation¶

The matrix is \(3 imes3\) with three possible values per position, each generated independently according to its weights.

Sample 3¶

Input¶

1 2
3 7

Output¶

Explanation¶

With one position, the only row and column are both constant, so the probability of passing is zero.

Constraints and Guarantees¶

\(1\le n\le5\) and \(1\le m\le7\) .
\(0\le w_{i,j,c}\le100000\) , and each position has at least one positive weight.

Test Groups¶

Score share	Additional conditions
100%	No additional conditions