# 犀牛坦克

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

犀牛坦克的设计团队用一个特征矩阵检验新型号。各位置的特征独立生成，但每个位置采用的概率分布可能不同。团队希望矩阵中每行、每列都具有变化，请计算一台坦克通过检验的概率。

## 形式化问题描述

随机生成一个 $n\times n$ 矩阵，每个元素属于 $\{1,\ldots,m\}$ .对于位置 $(i,j)$ ，给定非负整数权重 $w_{i,j,1},\ldots,w_{i,j,m}$ ，其取值为 $c$ 的概率为

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

所有位置相互独立。如果不存在元素全相同的行，也不存在元素全相同的列，矩阵就合格。求矩阵合格的概率。

令 $P=10^9+7$ .将答案写成分数 $a/b$ ，输出 $a\cdot b^{-1}\bmod P$ ，其中 $b^{-1}$ 为模 $P$ 乘法逆元。给定范围保证每个位置的权重和在 $1$ 到 $P-1$ 之间，因此该表示存在。

## 输入格式

第一行两个整数 $n,m$ .接下来 $n^2$ 行，按矩阵从上到下、每行从左到右的顺序描述各位置。每行 $m$ 个整数，依次为该位置取值 $1$ 到 $m$ 的权重。

## 输出格式

输出一个整数，表示合格概率的模 $P$ 表示。

## 样例 1

### 输入

```text
2 2
1 1
1 1
1 1
1 1
```

### 输出

```text
125000001
```

### 解释

共有 $16$ 个等概率矩阵，其中两种棋盘格排列合格，概率为 $1/8$ ，对应模值为 $125000001$ .

## 样例 2

### 输入

```text
3 3
1 1 2
3 2 1
0 0 3
1 0 2
0 3 5
1 2 3
6 7 9
3 2 1
1 1 1
```

### 输出

```text
875789148
```

### 解释

矩阵为 $3	imes3$ ，每个位置有三种特征，按各自权重独立生成。

## 样例 3

### 输入

```text
1 2
3 7
```

### 输出

```text
0
```

### 解释

只有一个位置时，唯一的行与列都满足“元素全相同”，所以合格概率为零。

## 数据范围与保证

- $1\le n\le5$ ，$1\le m\le7$ .
- $0\le w_{i,j,c}\le100000$ ，每个位置至少有一个正权重。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |