1981：划分
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：2
解决：2
题目描述
给定一个长度为 $n$ 的排列 $p_1,p_2,...,p_n$，请你将其划分成 $m$ 个连续段，并最大化每个连续段中最大值的和，并求出取到该最大值有多少种方案？方案数对 $10^9+7$ 取模
输入
输入共两行：
第一行，两个正整数 $n,m$ 表示排列的长度和划分的段数
第二行，$n$ 个正整数，表示给定的排列
$1\le m\le n\le 10^5$
$1\le p_i\le 10^9$
输出
输出共两行：
第一行，一个正整数表示划分后能取到的最大和
第二行，一个正整数，表示方案数对 $10^9+7$ 取模
样例输入-1 复制
4 2
4 1 3 2样例输出-1 复制
7
2样例输入-2 复制
4 4
3 2 1 4样例输出-2 复制
10
1提示
样例解释1：两种划分方法能取到 $7$
方案1：$[4].[1,3,2]$ 第一段最大值是 $4$，第二段最大值是 $3$, 总和是 $7$
方案2：$[4,1],[3,2]$ 第一段最大值是 $4$，第二段最大值是 $3$, 总和是 $7$
