Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

C. Разбиения перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$ и целое число $$$k$$$, такое что $$$1 \leq k \leq n$$$. Перестановка обозначает, что каждое значение от $$$1$$$ до $$$n$$$ содержится в $$$p$$$ ровно один раз.

Рассмотрим все разбиения этой перестановки на $$$k$$$ отрезков. Формально, такое разбиение это множество отрезков $$$\{[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\}$$$, такое что:

  • $$$1 \leq l_i \leq r_i \leq n$$$ для всех $$$1 \leq i \leq k$$$.
  • Для всех $$$1 \leq j \leq n$$$ существует ровно один отрезок $$$[l_i, r_i]$$$, такой что $$$l_i \leq j \leq r_i$$$.

Два разбиения считаются различными, если существует отрезок, лежащий в одном разбиении, но не лежащий в другом.

Давайте посчитаем значение разбиения $$$\sum\limits_{i=1}^{k} {\max\limits_{l_i \leq j \leq r_i} {p_j}}$$$ для всех возможных разбиений перестановки на $$$k$$$ отрезков. Ваша задача найти максимальное значение разбиения по всем таким разбиениям и количество таких разбиений, значение которых равно максимально возможному. Поскольку второе число может быть слишком большим, вы должны найти его остаток при делении на $$$998\,244\,353$$$.

Входные данные

В первой строке находится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 200\,000$$$) — размер перестановки и количество отрезков в разбиениях.

Во второй строке находится $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — данная перестановка.

Выходные данные

Выведите два целых числа — максимальное возможное значение разбиения по всем разбиениям перестановки на $$$k$$$ отрезков и количество таких разбиений, для которых значение равно максимальному возможному значению по модулю $$$998\,244\,353$$$.

Обратите внимание, вы должны найти только второе число по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3 2
2 1 3
Выходные данные
5 2
Входные данные
5 5
2 1 5 3 4
Выходные данные
15 1
Входные данные
7 3
2 7 3 1 5 4 6
Выходные данные
18 6
Примечание

В первом тесте, существует только два разбиения при $$$k = 2$$$: $$$\{[1, 1], [2, 3]\}$$$ и $$$\{[1, 2], [3, 3]\}$$$. Для каждого из них значение разбиения равно $$$2 + 3 = 5$$$. Поэтому максимальное возможное значение разбиения это $$$5$$$ и количество разбиений равно $$$2$$$.

Во третьем тесте при $$$k = 3$$$, разбиения, для которых значение равно максимальному возможному это $$$\{[1, 2], [3, 5], [6, 7]\}$$$, $$$\{[1, 3], [4, 5], [6, 7]\}$$$, $$$\{[1, 4], [5, 5], [6, 7]\}$$$, $$$\{[1, 2], [3, 6], [7, 7]\}$$$, $$$\{[1, 3], [4, 6], [7, 7]\}$$$, $$$\{[1, 4], [5, 6], [7, 7]\}$$$. Для всех этих разбиений их значение равно $$$7 + 5 + 6 = 18$$$.

Разбиение $$$\{[1, 2], [3, 4], [5, 7]\}$$$, например, имеет значение $$$7 + 3 + 6 = 16$$$, что меньше чем максимальное возможное, поэтому мы его не считаем.