[HAOI2008]木棍分割

有 $n$ 根木棍，第 $i$ 根木棍的长度为 $L_i$。这 $n$ 根木棍依次连结在一起，总共有 $n-1$ 个连接处。

现在允许你最多砍断 $m$ 个连接处，砍完后 $n$ 根木棍被分成了若干段。你需要：

1. 使总长度最大的一段的长度最小；
2. 在此前提下，求有多少种砍的方法能达到这个最小值，答案对 $10007$ 取模。

输入格式

第一行包含两个整数 $n, m$，分别表示木棍根数和最多可砍断的连接处数目。

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

输出格式

输出一行两个整数：第一个数是总长度最大的一段的长度的最小值，第二个数是达到该最小值的砍法数量对 $10007$ 取模的结果。

样例输入

3 2
1
1
10

样例输出

10 2

样例解释

三根木棍长度依次为 $1, 1, 10$，最多可砍断 $2$ 处。最长段的长度最小值为 $10$，有两种砍法达到它：

$$(1)(1)(10)\qquad\text{和}\qquad(1\ 1)(10).$$

数据范围

对于所有测试数据：

• $1\le n\le 5\times 10^4$；
• $0\le m\le \min(n-1, 1000)$；
• $1\le L_i\le 1000$。

来源与许可

本题为 HAOI 2008 试题「木棍分割」，题面与测试数据整理自 BZOJ 1044。

样例 1

输入

3 2
1
1
10

输出

10 2