有 $n$ 名球员定期参加排球训练。教练 Igor 非常了解他们的能力：$a_i$ 是第 $i$ 名球员的技能水平。每次训练课包含一系列比赛，对于每场比赛，教练会选择两支互不相交的队伍，每支队伍各有 $k$ 名球员。队伍的技能水平定义为该队所有球员技能水平之和。

教练注意到，两支队伍技能水平之间的差值（即差值的绝对值）越大，比赛结束得越快。比赛结束得越快，单次训练课中就能进行更多的比赛！因此，他决定以最大化两队技能水平差值的方式来选择队伍。

请帮助 Igor 规划整个训练课。找出两支队伍技能水平之间可能的最大差值，并计算达到该最大差值的比赛场数，结果对 $10^9 + 7$ 取模。

比赛不能重复，这意味着两支队伍最多只能进行一次比赛。例如，对于 $n = 4$ 和 $k = 2$，只有三种可能的比赛：球员 1 和 2 对阵球员 3 和 4；或者球员 1 和 3 对阵球员 2 和 4；或者球员 1 和 4 对阵球员 2 和 3。

输入格式

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2000$；$1 \le k \le \frac{n}{2}$），分别表示可用球员的数量和每支队伍的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$），表示每名球员的技能水平。

输出格式

输出两个整数——两队技能水平的最大差值，以及达到该最大差值的比赛场数除以 $10^9 + 7$ 的余数。

样例

输入 1

6 2
2 5 7 2 5 2

输出 1

8 6

输入 2

5 2
1 1 1 1 1

输出 2

0 15

说明

在第一个样例测试中，教练为每场比赛选择了两支 $k = 2$ 人的队伍。他可以组织 6 场技能水平差值为 8 的比赛。比赛如下图所示。例如，在第一场比赛中，球员 1 和 4 对阵球员 2 和 3，技能水平差值为：$|(a_1 + a_4) - (a_2 + a_3)| = |(2 + 2) - (5 + 7)| = 8$。

在第二个样例测试中，所有球员的技能水平相同，因此两队技能水平的差值始终为 0。因此，所有 15 场可能的比赛的最大差值均为 0。