Решение задачи Разбиения перестановки с Codeforces

Вам дана перестановка p1,p2,…,pn целых чисел от 1 до n и целое число k, такое что 1≤k≤n. Перестановка обозначает, что каждое значение от 1 до n содержится в p ровно один раз.

Рассмотрим все разбиения этой перестановки на k отрезков. Формально, такое разбиение это множество отрезков {[l1,r1],[l2,r2],…,[lk,rk]}, такое что:

1≤li≤ri≤n для всех 1≤i≤k.
Для всех 1≤j≤n существует ровно один отрезок [li,ri], такой что li≤j≤ri.
Два разбиения считаются различными, если существует отрезок, лежащий в одном разбиении, но не лежащий в другом.

Давайте посчитаем значение разбиения ∑i=1kmaxli≤j≤ripj для всех возможных разбиений перестановки на k отрезков. Ваша задача найти максимальное значение разбиения по всем таким разбиениям и количество таких разбиений, значение которых равно максимально возможному. Поскольку второе число может быть слишком большим, вы должны найти его остаток при делении на 998244353.