题目描述

有 $n$ 根木棍， 第 $i$ 根木棍的长度为 $L_i$，$n$根木棍依次连结了一起， 总共有 $n-1$ 个连接处。 现在允许你最多砍断 $m$ 个连接处， 砍完后 $n$ 根木棍被分成了很多段，要求满足总长度最大的一段长度最小， 并且输出有多少种砍的方法使得总长度最大的一段长度最小。 并将结果 mod 10007。。。

输入格式

第一行有 $2$ 个数 $n,m$。 接下来 $n$ 行每行一个正整数 $L_i$,表示第 $i$ 根木棍的长度。

输出格式

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

样例数据

3 2                           
1 
1
10

10 2

样例说明

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

数据范围

$n \leq 50000, 0 \leq m \leq min(n-1,1000), 1 \leq Li \leq 1000$