题目描述

给定一个长度为 $n$ 的排列 $p_1,p_2,...,p_n$，请你将其划分成 $m$ 个连续段，并最大化每个连续段中最大值的和，并求出取到该最大值有多少种方案？（方案数对$10^9+7$取模）

输入格式

输入共两行： 第一行，两个正整数 $n,m$ 表示排列的长度和划分的段数。 第二行，$n$ 个正整数，表示给定的排列。

输出格式

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

4 2
4 1 3 2

7
2

样例解释 1

两种划分方法能取到7 方案1： 4 | 1 3 2 --> 第一段最大值是4、第二段最大值是3，总和为7 方案2： 4 1 | 3 2 --> 第一段最大值是4、第二段最大值是3，总和为7

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$