题目描述

禾木正在玩一款游戏 —— 《核桃志·战略版》。在这个游戏中，他将管理一个伟大的帝国，并在这个帝国中 建造城市 ，征服遗迹 。

禾木的帝国有 $n$ 座城市。为了征服遗迹，他计划在每个城市建造一座纪念碑（遗迹只能通过纪念碑来征服）。这个游戏是回合制的，由于禾木是一位菜鸟玩家，所以每一回合禾木只能建造一座纪念碑。

在地图中有 $m$ 个遗迹需要禾木使用纪念碑来征服。禾木知道每个遗迹与城市之间的距离。

纪念碑的工作流程是这样的：

• 首次建成的那一回合（第 $1$ 回合），纪念碑可以控制所有与它距离不超过 $1$ 的遗迹；
• 第 $2$ 回合，纪念碑可以控制所有与它距离不超过 $2$ 的遗迹；
• 第 $3$ 回合，纪念碑可以控制所有与它距离不超过 $3$ 的遗迹；
• 以此类推……

禾木将在 $n$ 回合内建造 $n$ 座纪念碑（每一回合他都会选择一个没有建造过纪念碑的城市并在这座城市建立纪念碑），并且他的帝国将征服所有处于纪念碑控制范围内的遗迹（只要一个遗迹能够被至少一个纪念碑控制则这个遗迹就算做被征服的）。

禾木想要统计在第 $n$ 回合结束的时候被征服的地点的数量。

同时，禾木建造纪念碑的策略是随机的。也就是说，在任意一个回合，对于所有没有建造纪念碑的城市，它们会在该回合建造纪念碑的概率是相同的。

所以禾木想计算被征服的遗迹数量的期望。请你帮助他计算一下。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，以一个空格分隔，分别表示城市和遗迹的数量（$1 \le n \le 20, 1 \le m \le 5 \cdot 10^4$）。

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

输出格式

可以证明最终征服遗迹的期望数量可以表述成一个不可约分的分数 $\frac{x}{y}$（即 $gcd(x,y)=1$）。你需要输出一个整数，表示这个最简分数 $\frac{x}{y}$ 模 $998 244 353$ 的结果 —— 即 $x \cdot y^{-1} \text{ mod } 998244353$，其中 $y^{-1}$ 满足 $y \cdot y^{-1} \text{ mod } 998244353 = 1$。

样例

3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3

166374062

样例 1 解释

纪念碑的建造过程可以看成一个个 $1$ 到 $n$ 的排列，我们依次来分析它们：

• $[1,2,3]$：第 $1$ 个纪念碑控制第 $1,4$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3,5$ 个遗迹，第 $3$ 个纪念碑控制第 $1$ 个遗迹。最终有 $4$ 个遗迹被征服。
• $[1,3,2]$：第 $1$ 个纪念碑控制第 $1,4$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3$ 个遗迹，第 $3$ 个纪念碑控制第 $1$ 个遗迹。最终有 $3$ 个遗迹被征服。
• $[2,1,3]$：第 $1$ 个纪念碑控制第 $1$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3,5$ 个遗迹，第 $3$ 个纪念碑控制第 $1$ 个遗迹。最终有 $3$ 个遗迹被征服。
• $[2,3,1]$：第 $1$ 个纪念碑控制第 $1$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3,5$ 个遗迹，第 $3$ 个纪念碑控制第 $1$ 个遗迹。最终有 $3$ 个遗迹被征服。
• $[3,1,2]$：第 $1$ 个纪念碑控制第 $1$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3$ 个遗迹，第 $3$ 个纪念碑控制第 $1,5$ 个遗迹。最终有 $3$ 个遗迹被征服。
• $[3,2,1]$：第 $1$ 个纪念碑控制第 $1$ 个遗迹，第 $2$ 个纪念碑控制第 $1,3,5$ 个遗迹，第 $3$ 个纪念碑控制第 $1,5$ 个遗迹。最终有 $3$ 个遗迹被征服。

所以最终征服遗迹的期望数量为 $\frac{4+3+3+3+3+3}{6} = \frac{19}{6} = 19 \cdot 6^{-1}$ $\equiv$ $19 \cdot 166374059 \equiv 166374062 (\text{ mod } 998244353)$ 。

数据范围

• 对于 $20\%$ 的数据，$n,m \le 5$；
• 对于 $40\%$ 的数据，$n \le 10, m \le 100$；
• 对于 $60\%$ 的数据，$n \le 15, m \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n \le 20, 1 \le m \le 5 \cdot 10^4$。