题目描述

有 $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\le 50000, 0\le m\le \min(n-1,1000),1\le L_i\le 1000$