Assimilation IV

题意翻译

- 给定 $n$ ($1 \le n \le 20$) 个城市和 $m$ ($1 \le m \le 5 \cdot 10^4$)个点. - 对于每个城市，给定所有点到该城市的距离与光在一秒内行走距离的比值 $d$ ($1 \le d \le n + 1$)（不一定满足三角不等式）. - 从第零秒开始，每隔一秒可以点亮一个未被点亮的城市. - 已知点亮城市的顺序随机，求第 n 秒的瞬间被照亮的点数的期望值,答案对 998244353 取模。

题目描述

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!

输入输出格式

输入格式

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.

输出格式

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 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

166374062

说明

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} $