E. Assimilation IV
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру Assimilation IV. В этой игре он управляет огромной империей: основывает города, отстраивает их и захватывает новые земли.

Сейчас в империи Монокарпа $$$n$$$ городов, и Монокарп планирует их развивать. Он собирается в каждом из этих городов построить по одному Монументу, и это поможет ему захватить новые территории. Игра пошаговая и, так как Монокарп еще не очень хорошо разбирается в игре, на каждом ходу он строит ровно один Монумент.

Монокарпа интересуют $$$m$$$ точек на карте, которые он хотел бы контролировать при помощи Монументов. Для каждой точки он знает расстояние от нее до каждого из своих городов. Монументы позволяют захватывать территорию следующим образом: в ход, в который Монокарп строит Монумент в некотором городе, строение позволяет ему контролировать все точки на расстоянии $$$1$$$ до этого города. На следующий ход Монумент будет контролировать все точки на расстоянии не более $$$2$$$, еще через ход — все точки на расстоянии $$$3$$$, и так далее. Монокарп собирается построить $$$n$$$ Монументов за $$$n$$$ ходов, и после этого его империи будут принадлежать каждая интересующая его точка, которая контролируется хотя бы одним Монументом.

Монокарп никак не может придумать оптимальную стратегию, и поэтому на каждом шагу он будет просто выбирать город случайно среди тех, в которых еще нет Монументов. Монокарп интересуется, сколько из $$$m$$$ точек он сможет контролировать к концу хода под номером $$$n$$$. Помогите Монокарпу посчитать математическое ожидание количества точек, которые он сможет контролировать!

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 20$$$; $$$1 \le m \le 5 \cdot 10^4$$$) — количество городов в империи Монокарпа и количество интересующих его точек, соответственно.

Далее следуют $$$n$$$ строк по $$$m$$$ чисел: $$$j$$$-е число в $$$i$$$-й строке $$$d_{i, j}$$$ ($$$1 \le d_{i, j} \le n + 1$$$) — это расстояние от $$$i$$$-го города до $$$j$$$-й интересующей Монокарпа точки.

Выходные данные

Можно показать, что математическое ожидание количества интересных точек, которые Монокарп сможет контролировать к концу хода $$$n$$$, представимо в виде несократимой дроби $$$\frac{x}{y}$$$. Выведите эту дробь по модулю $$$998\,244\,353$$$ (значение $$$x \cdot y^{-1} \bmod 998244353$$$, где $$$y^{-1}$$$ — такое число, что $$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

Пример
Входные данные
3 5
1 4 4 3 4
1 4 1 4 2
1 4 4 4 3
Выходные данные
166374062
Примечание

Рассмотрим все возможные порядки городов постройки Монументов:

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