Предположим, вам задан целочисленный массив \(a_1, a_2, \dots, a_n\).
Пусть \(\operatorname{lsl}(i)\) равно количеству индексов \(j\) (\(1 \le j < i\)) таких, что \(a_j < a_i\).
Аналогично, пусть \(\operatorname{grr}(i)\) равно количеству индексов \(j\) (\(i < j \le n\)) таких, что \(a_j > a_i\).
Назовем позицию \(i\) в массиве \(a\) хорошей, если \(\operatorname{lsl}(i) < \operatorname{grr}(i)\).
Наконец, определим функцию \(f\) на массиве \(a\) \(f(a)\) как сумму всех \(a_i\) таких, что \(i\) — хорошая в \(a\).
Для заданных целых чисел \(n\) и \(k\), посчитайте сумму \(f(a)\) по всем массивам \(a\) размера \(n\) таких, что \(1 \leq a_i \leq k\) для всех \(1 \leq i \leq n\), по модулю \(998\,244\,353\).
Выходные данные
Выведите единственное число — сумму \(f\) по всем массивам \(a\) размера \(n\) по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных:
| \(f([1,1,1]) = 0\) | \(f([2,2,3]) = 2 + 2 = 4\) |
| \(f([1,1,2]) = 1 + 1 = 2\) | \(f([2,3,1]) = 2\) |
| \(f([1,1,3]) = 1 + 1 = 2\) | \(f([2,3,2]) = 2\) |
| \(f([1,2,1]) = 1\) | \(f([2,3,3]) = 2\) |
| \(f([1,2,2]) = 1\) | \(f([3,1,1]) = 0\) |
| \(f([1,2,3]) = 1\) | \(f([3,1,2]) = 1\) |
| \(f([1,3,1]) = 1\) | \(f([3,1,3]) = 1\) |
| \(f([1,3,2]) = 1\) | \(f([3,2,1]) = 0\) |
| \(f([1,3,3]) = 1\) | \(f([3,2,2]) = 0\) |
| \(f([2,1,1]) = 0\) | \(f([3,2,3]) = 2\) |
| \(f([2,1,2]) = 1\) | \(f([3,3,1]) = 0\) |
| \(f([2,1,3]) = 2 + 1 = 3\) | \(f([3,3,2]) = 0\) |
| \(f([2,2,1]) = 0\) | \(f([3,3,3]) = 0\) |
| \(f([2,2,2]) = 0\) | |
Сложив все значения, получаем ответ, равный \(28\).