CF1525E.Assimilation IV

Monocarp is playing a game "Assimilation IV". In this game he manages a great empire: builds cities and conquers new lands.

Monocarp's empire has $n$ cities. In order to conquer new lands he plans to build one Monument in each city. The game is turn-based and, since Monocarp is still amateur, he builds exactly one Monument per turn.

Monocarp has $m$ points on the map he'd like to control using the constructed Monuments. For each point he knows the distance between it and each city. Monuments work in the following way: when built in some city, a Monument controls all points at distance at most $1$ to this city. Next turn, the Monument controls all points at distance at most $2$, the turn after — at distance at most $3$, and so on. Monocarp will build $n$ Monuments in $n$ turns and his empire will conquer all points that are controlled by at least one Monument.

Monocarp can't figure out any strategy, so during each turn he will choose a city for a Monument randomly among all remaining cities (cities without Monuments). Monocarp wants to know how many points (among $m$ of them) he will conquer at the end of turn number $n$. Help him to calculate the expected number of conquered points!

莫诺卡普正在玩一款名为“同化 IV”的游戏。在这款游戏中，他管理着一个庞大的帝国：建造城市并征服新的领土。

莫诺卡普的帝国拥有 $n$ 座城市。为了征服新领土，他计划在每座城市中建造一座纪念碑。游戏以回合制进行；由于莫诺卡普尚属新手，他每回合恰好建造一座纪念碑。

莫诺卡普的地图上有 $m$ 个他希望借助所建纪念碑加以控制的点。对于每个点，他已知其到每座城市的距离。纪念碑的工作机制如下：当在某座城市中建成时，该纪念碑在当回合即可控制所有到该城市的距离不超过 $1$ 的点；下一回合，它可控制所有到该城市的距离不超过 $2$ 的点；再下一回合，可控制所有到该城市的距离不超过 $3$ 的点，依此类推。莫诺卡普将在 $n$ 回合内于 $n$ 座城市中各建造一座纪念碑，他的帝国最终将征服所有被至少一座纪念碑控制的点。

莫诺卡普尚未掌握任何策略，因此在每一回合中，他将从所有尚未建造纪念碑的城市（即剩余未选城市）中随机选择一座来建造纪念碑。莫诺卡普想知道：在第 $n$ 回合结束时，他总共能征服多少个点（共 $m$ 个点）？请帮他计算被征服点数的期望值！

The first line contains two integers $n$ and $m$ ($1 \le n \le 20$; $1 \le m \le 5 \cdot 10^4$) — the number of cities and the number of points.

Next $n$ lines contains $m$ integers each: the $j$-th integer of the $i$-th line $d_{i, j}$ ($1 \le d_{i, j} \le n + 1$) is the distance between the $i$-th city and the $j$-th point.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 20$；$1 \le m \le 5 \cdot 10^4$）—— 分别表示城市的数量和点的数量。

接下来的 $n$ 行，每行包含 $m$ 个整数：第 $i$ 行的第 $j$ 个整数 $d_{i, j}$（$1 \le d_{i, j} \le n + 1$）表示第 $i$ 个城市与第 $j$ 个点之间的距离。

It can be shown that the expected number of points Monocarp conquers at the end of the $n$-th turn can be represented as an irreducible fraction $\frac{x}{y}$. Print this fraction modulo $998\,244\,353$, i. e. value $x \cdot y^{-1} \bmod 998244353$ where $y^{-1}$ is such number that $y \cdot y^{-1} \bmod 998244353 = 1$.

可以证明，Monocarp 在第 $n$ 回合结束时所占领的点数的期望值可表示为一个既约分数 $\frac{x}{y}$。请输出该分数对 $998\,244\,353$ 取模的结果，即 $x \cdot y^{-1} \bmod 998244353$，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \bmod 998244353 = 1$ 的数。

Let's look at all possible orders of cities Monuments will be build in:

• $[1, 2, 3]$:
  • the first city controls all points at distance at most $3$, in other words, points $1$ and $4$;
  • the second city controls all points at distance at most $2$, or points $1$, $3$ and $5$;
  • the third city controls all points at distance at most $1$, or point $1$.In total, $4$ points are controlled.
• $[1, 3, 2]$: the first city controls points $1$ and $4$; the second city — points $1$ and $3$; the third city — point $1$. In total, $3$ points.
• $[2, 1, 3]$: the first city controls point $1$; the second city — points $1$, $3$ and $5$; the third city — point $1$. In total, $3$ points.
• $[2, 3, 1]$: the first city controls point $1$; the second city — points $1$, $3$ and $5$; the third city — point $1$. In total, $3$ points.
• $[3, 1, 2]$: the first city controls point $1$; the second city — points $1$ and $3$; the third city — points $1$ and $5$. In total, $3$ points.
• $[3, 2, 1]$: the first city controls point $1$; the second city — points $1$, $3$ and $5$; the third city — points $1$ and $5$. In total, $3$ points.

The expected number of controlled points is $\frac{4 + 3 + 3 + 3 + 3 + 3}{6}$ $=$ $\frac{19}{6}$ or $19 \cdot 6^{-1}$ $\equiv$ $19 \cdot 166374059$ $\equiv$ $166374062$ $\pmod{998244353}$

我们来考察所有可能的城市建造纪念碑的顺序：

• $[1, 2, 3]$：
  • 第一个城市控制所有距离不超过 $3$ 的点，即点 $1$ 和 $4$；
  • 第二个城市控制所有距离不超过 $2$ 的点，即点 $1$、$3$ 和 $5$；
  • 第三个城市控制所有距离不超过 $1$ 的点，即点 $1$。
    总共控制了 $4$ 个点。
• $[1, 3, 2]$：第一个城市控制点 $1$ 和 $4$；第二个城市控制点 $1$ 和 $3$；第三个城市控制点 $1$。总共控制了 $3$ 个点。
• $[2, 1, 3]$：第一个城市控制点 $1$；第二个城市控制点 $1$、$3$ 和 $5$；第三个城市控制点 $1$。总共控制了 $3$ 个点。
• $[2, 3, 1]$：第一个城市控制点 $1$；第二个城市控制点 $1$、$3$ 和 $5$；第三个城市控制点 $1$。总共控制了 $3$ 个点。
• $[3, 1, 2]$：第一个城市控制点 $1$；第二个城市控制点 $1$ 和 $3$；第三个城市控制点 $1$ 和 $5$。总共控制了 $3$ 个点。
• $[3, 2, 1]$：第一个城市控制点 $1$；第二个城市控制点 $1$、$3$ 和 $5$；第三个城市控制点 $1$ 和 $5$。总共控制了 $3$ 个点。

受控点数的期望值为 $\frac{4 + 3 + 3 + 3 + 3 + 3}{6}$ $=$ $\frac{19}{6}$，即 $19 \cdot 6^{-1}$ $\equiv$ $19 \cdot 166374059$ $\equiv$ $166374062$ $\pmod{998244353}$