В мире телесериала «Человек в высоком замке» есть \(m\) различных окончаний фильмов.
Абендсен владеет складом и книжной полкой. Сначала у него есть \(n\) фильмов на полке в определенном порядке. В месяц номер \(i\) он будет делать следующее:
- Он очистит полностью склад.
- Положит \(k_i \cdot m\) фильмов на склад, по \(k_i\) фильмов с каждым окончанием.
- Задаст себе вопрос — если он переложит все фильмы с полки на склад, потом случайно выберет \(n\) фильмов (из всех фильмов на складе) и переставит их на полку в случайном порядке, то какая вероятность того, что последовательность окончаний на отрезке \([l_i, r_i]\) на полке не изменится? Учтите, что он только задает себе такой вопрос, поэтому книги на полке не меняются.
Ответьте на все вопросы Абендсена.
Вероятность можно представить как дробь \(P_i\). Пусть \(A_i\) — это общее количество способов выбрать \(n\) фильмов со склада в \(i\)-й месяц. Тогда \(P_i \cdot A_i\) всегда является целым числом. Для каждого месяца выведите \(P_i \cdot A_i \pmod {998244353}\).
\(998244353\) — простое число и оно равно \(119 \cdot 2^{23} + 1\).
Гарантируется, что будет не более \(100\) различных значений \(k\).
Выходные данные
Выведите ответ на каждый запрос на отдельной строке.
Примечание
В первом запросе для второго запроса после добавления \(2 \cdot m\) фильмов на склад, склад будет выглядеть так: \(\{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4\}\).
Всего есть \(26730\) способа выбрать фильмы так, чтобы окончания \(e_l, e_{l+1}, \ldots, e_r\) не изменились, например, \([1, 2, 3, 2, 2]\) и \([1, 2, 3, 4, 3]\).
Всего есть \(2162160\) способов выбрать фильмы, поэтому вам нужно вывести \((\frac{26730}{2162160} \cdot 2162160) \mod 998244353 = 26730\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4 4
1 2 3 4 4 4
1 4 0
1 3 2
1 4 2
1 5 2
|
6
26730
12150
4860
|
|
2
|
5 5 3
1 2 3 4 5
1 2 100000
1 4 4
3 5 5
|
494942218
13125
151632
|