CF1326C.Permutation Partitions

You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ and an integer $k$, such that $1 \leq k \leq n$. A permutation means that every number from $1$ to $n$ is contained in $p$ exactly once.

Let's consider all partitions of this permutation into $k$ disjoint segments. Formally, a partition is a set of segments ${[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]}$, such that:

• $1 \leq l_i \leq r_i \leq n$ for all $1 \leq i \leq k$;
• For all $1 \leq j \leq n$ there exists exactly one segment $[l_i, r_i]$, such that $l_i \leq j \leq r_i$.

Two partitions are different if there exists a segment that lies in one partition but not the other.

Let's calculate the partition value, defined as $\sum\limits_{i=1}^{k} {\max\limits_{l_i \leq j \leq r_i} {p_j}}$, for all possible partitions of the permutation into $k$ disjoint segments. Find the maximum possible partition value over all such partitions, and the number of partitions with this value. As the second value can be very large, you should find its remainder when divided by $998\,244\,353$.

给你一个由 $1$ 到 $n$ 的整数构成的排列 $p_1, p_2, \ldots, p_n$，以及一个整数 $k$，满足 $1 \leq k \leq n$。所谓排列，是指每个从 $1$ 到 $n$ 的整数在 $p$ 中恰好出现一次。

考虑该排列的所有划分为 $k$ 个互不相交段（segments）的方式。形式上，一种划分是一组段 $\{[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\}$，满足：

• 对所有 $1 \leq i \leq k$，有 $1 \leq l_i \leq r_i \leq n$；
• 对所有 $1 \leq j \leq n$，存在恰好一个段 $[l_i, r_i]$，使得 $l_i \leq j \leq r_i$。

若存在某个段属于一个划分但不属于另一个划分，则称这两个划分不同。

对每种将排列划分为 $k$ 个互不相交段的方式，我们定义其划分值为

$$\sum\limits_{i=1}^{k} {\max\limits_{l_i \leq j \leq r_i} {p_j}}.$$

请找出所有此类划分中可能达到的最大划分值，以及达到该最大值的划分数量。由于该数量可能非常大，请输出它对 $998\,244\,353$ 取模的结果。

The first line contains two integers, $n$ and $k$ ($1 \leq k \leq n \leq 200\,000$) — the size of the given permutation and the number of segments in a partition.

The second line contains $n$ different integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$) — the given permutation.

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 200\,000$）—— 分别表示给定排列的长度以及划分中区间的个数。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）—— 给定的排列。

Print two integers — the maximum possible partition value over all partitions of the permutation into $k$ disjoint segments and the number of such partitions for which the partition value is equal to the maximum possible value, modulo $998\,244\,353$.

Please note that you should only find the second value modulo $998\,244\,353$.

输出两个整数：在将该排列划分为 $k$ 个互不相交的段的所有划分方案中，划分值的最大可能值；以及使得划分值等于该最大可能值的划分方案数目（对 $998\,244\,353$ 取模）。

请注意，你只需将第二个数值对 $998\,244\,353$ 取模。

In the first test, for $k = 2$, there exists only two valid partitions: ${[1, 1], [2, 3]}$ and ${[1, 2], [3, 3]}$. For each partition, the partition value is equal to $2 + 3 = 5$. So, the maximum possible value is $5$ and the number of partitions is $2$.

In the third test, for $k = 3$, the partitions with the maximum possible partition value are ${[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]}$. For all of them, the partition value is equal to $7 + 5 + 6 = 18$.

The partition ${[1, 2], [3, 4], [5, 7]}$, however, has the partition value $7 + 3 + 6 = 16$. This is not the maximum possible value, so we don't count it.

在第一个测试用例中，当 $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$，未达到最大可能值，因此不计入统计。