题目说明

你有$n$个数$a_1,a_2,a...a_n$，你想将它们重排，也就是找到一个 $1 ∼ n$的排列$a_{p_1},a_{p_2},...,a_{p_n}$，使得$\sum_{i=1}^{n-1}|a_{p_i}-a_{p_{i+1}}|$最大。 但是这个太简单了，所以你还要输出有多少种不同的方案。但是这个还是太简单了， 所以你要输出$\sum_{i=1}^{n-1}|a_{p_i}-a_{p_{i+1}}|$的前$k$大的不同的值和每个值对应的方案数。由于方 案数可能很大，输出对$10^9 + 7$ 取模的结果。

输入格式

第一行，两个整数$n,k$。 接下来一行，$n$个整数$a_1,a_2,...,a_n$。

输出格式

共$k$行，每行两个整数，表示绝对值之和的取值和有多少种方案。如果不存在这个值，也就是说不同的取值不足$k$个，那么在这一行输出两个−1。

4 8
1 3 7 9

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% 的数据，满足 $1 ≤ n ≤ 600,1 ≤ k ≤ 20,1 ≤ a_i ≤ 10^6$。

附件

附件下载