题目描述 给定一个长度为 n n 的排列 p 1 , p 2 , . . . , p n p 1 ​ ,p 2 ​ ,...,p n ​ ，请你将其划分成 m m 个连续段，并最大化每个连续段中最大值的和，并求出取到该最大值有多少种方案？（方案数对 1 0 9 + 7 10 9 +7取模）

输入格式 输入共两行： 第一行，一个正整数 n n 表示排列的长度。 第二行， n n 个正整数，表示给定的排列。

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

数据范围 对于 30 % 30% 的数据， 1 ≤ m ≤ n ≤ 20 1≤m≤n≤20 对于 60 % 60% 的数据， 1 ≤ m ≤ n ≤ 1 0 3 1≤m≤n≤10 3

对于 100 % 100% 的数据， 1 ≤ m ≤ n ≤ 1 0 5 1≤m≤n≤10 5

样例数据 输入: 4 2 4 1 3 2 输出: 7 2 说明: 两种划分方法能取到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