В чемпионате Берляндии по многоборью участвуют n спортсменов. Соревнование состоит из k этапов, на каждом из которых участник может набрать любое вещественное число очков в диапазоне от 0 до 1.

Маленький мальчик Олег любит спортивную аналитику, и поэтому хочет осветить чемпионат в своём спортивном блоге. Олег ничего не знает ни про спортсменов, ни про ход соревнования. Зато Олег знаком с теорией вероятностей, поэтому он предполагает, что каждый спортсмен на каждом этапе набирает случайное число очков, равномерно распределенное на отрезке [0, 1]. Также Олег считает, что результаты всех спортсменов на всех этапах в совокупности независимы.

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

Обратите внимание, что в справедливой таблице один спортсмен может стоять выше другого, даже если он проиграл ему на всех этапах. Пусть, например, в соревновании из двух этапов очки спортсмена 1 равны (0.2, 0.2), очки спортсмена 2 равны (0.8, 0.8), а очки спортсмена 3 равны (0, 1). Тогда таблица (1, 3, 2) является справедливой, поскольку спортсмен 1 обогнал спортсмена 3 на первом этапе, а спортсмен 3 обогнал спортсмена 2 на втором; при этом спортсмен 1 проиграл спортсмену 2 на каждом из этапов.

Чемпионат еще не начался, но Олег уже хочет зарезервировать достаточно места на хостинге, чтобы все таблицы поместились на сервер. Для этого он просит вас посчитать математическое ожидание количества способов составить справедливую рейтинговую таблицу по итогам соревнований. Олег также хочет проверить свои навыки в теории чисел, поэтому он хочет получить ответ по модулю P = 998 244 353. Формально, если ответ на задачу представленный в виде несократимой дроби равен A / B, вам следует вывести такое целое число x, что 0 ≤ x < P и A ≡ B·x ± od P (гарантируется, что такое число x существует и единственно).

Математическое ожидание величины, принимающей целые значения, определяется как , где суммирование происходит по всем целым числам, а p_x — вероятность того, что величина принимает значение x.