Монокарп играет в компьютерную игру Assimilation IV. В этой игре он управляет огромной империей: основывает города, отстраивает их и захватывает новые земли.
Сейчас в империи Монокарпа \(n\) городов, и Монокарп планирует их развивать. Он собирается в каждом из этих городов построить по одному Монументу, и это поможет ему захватить новые территории. Игра пошаговая и, так как Монокарп еще не очень хорошо разбирается в игре, на каждом ходу он строит ровно один Монумент.
Монокарпа интересуют \(m\) точек на карте, которые он хотел бы контролировать при помощи Монументов. Для каждой точки он знает расстояние от нее до каждого из своих городов. Монументы позволяют захватывать территорию следующим образом: в ход, в который Монокарп строит Монумент в некотором городе, строение позволяет ему контролировать все точки на расстоянии \(1\) до этого города. На следующий ход Монумент будет контролировать все точки на расстоянии не более \(2\), еще через ход — все точки на расстоянии \(3\), и так далее. Монокарп собирается построить \(n\) Монументов за \(n\) ходов, и после этого его империи будут принадлежать каждая интересующая его точка, которая контролируется хотя бы одним Монументом.
Монокарп никак не может придумать оптимальную стратегию, и поэтому на каждом шагу он будет просто выбирать город случайно среди тех, в которых еще нет Монументов. Монокарп интересуется, сколько из \(m\) точек он сможет контролировать к концу хода под номером \(n\). Помогите Монокарпу посчитать математическое ожидание количества точек, которые он сможет контролировать!
Выходные данные
Можно показать, что математическое ожидание количества интересных точек, которые Монокарп сможет контролировать к концу хода \(n\), представимо в виде несократимой дроби \(\frac{x}{y}\). Выведите эту дробь по модулю \(998\,244\,353\) (значение \(x \cdot y^{-1} \bmod 998244353\), где \(y^{-1}\) — такое число, что \(y \cdot y^{-1} \bmod 998244353 = 1\)).
Примечание
Рассмотрим все возможные порядки городов постройки Монументов:
- \([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}\)