题目描述

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

输入格式

输入文件第一行有 $2$ 个数 $n,m$。

接下来 $n$ 行每行一个正整数 $l_i$，表示第 $i$ 根木棍的长度。

输出格式

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

3 2
1 
1
10

10 2

样例说明

两种砍的方法：$(1)(1)(10)$ 和 $(1,1)(10)$。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5\times10^4$，$0\le m\le \min(n-1,10^3)$，$1\le l_i\le10^3$。