Assimilation IV
Contest: Educational Codeforces Round 109 (Rated for Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dp, math, probabilities, two pointers

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!

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3

Example output:
166374062

Editorial:
Let $$$I(j)$$$ be the indicator function equal to $$$1$$$ if the $$$j$$$-th point is controlled by any city and $$$0$$$ otherwise. Then the expected number of controlled points $$$ans$$$ can be written as $$$E(\sum\limits_{j=1}^{m}{I(j)}) = \sum\limits_{j=1}^{m}{E(I(j))}$$$ (by linearity of expected value).
The expected value of the indicator function is equal to the probability of this function equal to $$$1$$$ ($$$E(I(j)) = P[I(j) = 1]$$$). In other words, for each point we need to calculate the probability of this point being controlled by any city.
Let's instead calculate the probability of point $$$j$$$ not being controlled by any city. Suppose, the distance between point $$$j$$$ and some city $$$i$$$ is equal to $$$x$$$. If we build a Monument in city $$$i$$$ at step $$$< n + 1 - x$$$ (zero indexed) then the point will be controlled by city $$$i$$$. But building the Monument at any step greater or equal than $$$n + 1 - x$$$ is fine.
Let's for each turn $$$k \in [0, n)$$$ calculate the number of cities that you can build Monument in starting this turn as $$$cnt[k]$$$. Our task is to calculate the number of permutations that are consistent with array $$$cnt$$$.
At first turn, we can choose one of $$$cnt[0]$$$ cities, at second turn we have $$$cnt[0] + cnt[1] - 1$$$ choices, at third step — $$$cnt[0] + cnt[1] + cnt[2] - 2$$$ choices, and so on. Using this idea, it's not hard to calculate the number of good permutations and then the initial probablity $$$P[I(j) = 1]$$$ $$$\equiv$$$ $$$1 - \text{good_permutations} \cdot (n!)^{-1} \pmod{998244353}$$$.
The expected value $$$ans \equiv \sum\limits_{j=1}^{m}{P[I(j) = 1]} \pmod{998244353}$$$.