#2179. [HAOI2008]木棍分割

[HAOI2008]木棍分割

题目描述

nn 根木棍, 第 ii 根木棍的长度为 lil_inn 根木棍依次连结了一起,总共有 n1n-1 个连接处。现在允许你最多砍断 mm 个连接处,砍完后 nn 根木棍被分成了很多段,要求满足总长度最大的一段长度最小,并且输出有多少种砍的方法使得总长度最大的一段长度最小。并将结果 mod(104+7)\bmod(10^4+7)

输入格式

输入文件第一行有 22 个数 n,mn,m

接下来 nn 行每行一个正整数 lil_i,表示第 ii 根木棍的长度。

输出格式

输出有 22 个数,第一个数是总长度最大的一段的长度最小值,第二个数是有多少种砍的方法使得满足条件。

3 2
1 
1
10

10 2

样例说明

两种砍的方法:(1)(1)(10)(1)(1)(10)(1,1)(10)(1,1)(10)

数据规模与约定

对于 100%100\% 的数据,1n5×1041\le n\le 5\times10^40mmin(n1,103)0\le m\le \min(n-1,10^3)1li1031\le l_i\le10^3