寻找最大和

问题描述

给定一个长度为$n$的排列$p_1, p_2, ..., p_n$，你需要将其划分成$m$个连续的段，并最大化每个连续段中最大值的和。同时，计算出达到最大和的分段方案数。最后，答案对$10^9 + 7$取模。

输入格式

• 第一行：两个正整数$n, m$，表示排列的长度和划分的段数。
• 第二行：一个长度为$n$的排列$p_1, p_2, ..., p_n$，表示给定的排列。

输出格式

• 输出共两行：
  • 第一行：一个正整数，表示划分后能取到的最大和。
  • 第二行：一个正整数，表示方案数对$10^9 + 7$取模。

4 2
4 1 3 2

7
2

4 4
3 2 1 4

10
1

数据范围

• 对于30%的数据，$1 \leq m \leq n \leq 20$。
• 对于60%的数据，$1 \leq m \leq n \leq 10^3$。
• 对于100%的数据，$1 \leq m \leq n \leq 10^5$。