排列计数

你有�个数�1 , �2 , …, �� ，你想将它们重排，也就是找到一个 1 ∼ �的排列 ��1 , ��2 , …, ��� ，使得 �−1 �=1 | ��� − ���+1 |最大。

但是这个太简单了，所以你还要输出有多少种不同的方案。但是这个还是太简单了， 所以你要输出 �−1 �=1 | ��� − ���+1 |的前�大的不同的值和每个值对应的方案数。由于方 案数可能很大，输出对109 + 7 取模的结果。

输入格式 第一行，两个整数�, �。

接下来一行，�个整数�1 , �2 , …, �� 。

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

样例输入 1 4 8 1 3 7 9

样例输出 1 20 2 18 4 16 2 14 8 12 2 10 4 8 2 -1 -1

样例输入输出 2 见下发文件。

数据规模 共 10 组数据，

测试点 1,2 满足，� ≤ 10。

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

测试点 4 满足，� ≤ 15。

测试点 5,6 满足，� = 1。 测试点 7,8 满足，� ≤ 100。

对于 100% 的数据，满足 1 ≤ � ≤ 600,1 ≤ � ≤ 20,1 ≤ �� ≤ 106 。