该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有 n个数$\red{ a_1, a_2, …,a_n}$ ，你想将它们重排，也就是找到一个 1 ∼ n的排列 $\red{a_{p1},a_{p2}, …,a_pn} ，使得$ $\red{\sum_{i=1}^{n-1} | a_{pi} - {a_{p_{i+1}}} |}$ 最大。

但是这个太简单了，所以你还要输出有多少种不同的方案。

但是这个还是太简单了，

所以你要输出 $\red{\sum_{i=1}^{n-1} | a_{pi} - {a_{p_{i+1}}} |}$ 的前k 大的不同的值和每个值对应的方案数。由于方案数可能很大，输出对$\red{10^9 + 7}$ 取模的结果。

输入格式

第一行，两个整数 n,k 。

接下来一行， n个整数 $\red{a_1,a_2, …a_n}$, 。

输出格式

共k行，每行两个整数，表示绝对值之和的取值和有多少种方案。

如果不存在这个值，也就是说不同的取值不足 k个，那么在这一行输出两个−1。

样例输入1

4 8
2 3 7 9

样例输出1

20 2
18 4 
16 2 
14 8 
12 2 
10 4 
8 2 
-1 -1

样例输入输出2

见文件。

数据规模

共 10组数据， 测试点 1,2满足， n≤ 10。

测试点 3满足， n≤ 15,k = 1。

测试点 4满足， n≤ 15。

测试点 5,6满足， k= 1。

测试点 7,8满足， n≤ 100。

对于 100%的数据，满足 $\red{1 ≤ n≤ 600,1 ≤ k≤ 20,1 ≤a_i ≤ 10^6}$。