Назовем красотой массива \(b_1, b_2, \ldots, b_n\) (\(n > 1\)) — \(\min\limits_{1 \leq i < j \leq n} |b_i - b_j|\). Рассмотрим некоторый массив \(a_1, a_2, \ldots a_n\) и число \(k\). Требуется подсчитать сумму красот всех подпоследовательностей данного массива длины ровно \(k\). Так как ответ может получиться достаточно большим, то выведите его по модулю \(998244353\).
Последовательность \(a\) является подпоследовательностью \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов.
Выходные данные
Выведите одно целое число — сумму красот всех подпоследовательностей данного массива длины ровно \(k\). Так как ответ может получиться достаточно большим, то выведите его по модулю \(998244353\).
Примечание
В первом примере существует \(4\) подпоследовательности длины \(3\) — \([1, 7, 3]\), \([1, 3, 5]\), \([7, 3, 5]\), \([1, 7, 5]\), каждая из которых имеет красоту \(2\), поэтому ответ \(8\).
Во втором примере, есть только одна подпоследовательность длины \(5\) — весь массив, красота которого равна \(|10-1| = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 7 3 5
|
8
|
|
2
|
5 5
1 10 100 1000 10000
|
9
|