Вы играете в компьютерную игру. В этой игре вам необходимо сразиться с \(n\) монстрами.
Чтобы защищаться от монстров, вам нужен щит. У каждого щита есть два параметра: текущая прочность \(a\) и уровень защиты \(b\). У каждого монстра есть только один параметр: его сила \(d\).
Если вы сражаетесь с монстром с силой \(d\), используя щит с текущей прочностью \(a\) и уровнем защиты \(b\), возможны три исхода:
- если \(a = 0\), вы получаете \(d\) урона;
- если \(a > 0\) и \(d \ge b\), вы не получаете урона, но прочность щита уменьшается на \(1\);
- если \(a > 0\) и \(d < b\), ничего не происходит.
Сила \(i\)-го монстра равна \(d_i\), и вам придется сразиться со всеми монстрами в случайном порядке (все \(n!\) порядков равновероятны). Вы можете использовать один из \(m\) различных щитов, у \(i\)-го щита прочность изначально равна \(a_i\), а уровень защиты равен \(b_i\). Для каждого щита посчитайте математическое ожидание полученного урона, если вы сразитесь со всеми \(n\) монстрами в случайном порядке, используя этот щит.
Выходные данные
Выведите \(m\) целых чисел, \(i\)-е из которых соответствует математическому ожиданию урона, который вы получите, используя \(i\)-й щит, следующим образом: можно доказать, что для каждого щита ответ — это несократимая дробь \(\dfrac{x}{y}\), где \(y\) и \(998244353\) — взаимно простые числа. Выведите значение \(x \cdot y^{-1} \bmod 998244353\), где \(y^{-1}\) — обратный элемент к \(y\) (\(y \cdot y^{-1} \bmod 998244353 = 1\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 1
2 1
1 2
|
665496237
1
|
|
2
|
3 3
4 2 6
3 1
1 2
2 3
|
0
8
665496236
|