Вам дана перестановка \(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\).
Выходные данные
Выведите два целых числа — максимальное возможное значение разбиения по всем разбиениям перестановки на \(k\) отрезков и количество таких разбиений, для которых значение равно максимальному возможному значению по модулю \(998\,244\,353\).
Обратите внимание, вы должны найти только второе число по модулю \(998\,244\,353\).
Примечание
В первом тесте, существует только два разбиения при \(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\), что меньше чем максимальное возможное, поэтому мы его не считаем.