← 返回题目列表

Codeforces · 1361/B

B. 约翰尼和大师

中文机器翻译题面 查看原题

约翰尼刚刚找到了新的、很棒的教程:“如何成为一名特级大师?”。教程讲述了许多对Johnny来说奇怪和意想不到的事情,比如你必须要有耐心或者非常重要的是解决许多越来越难的问题。

男孩找到了一位在线评委,其任务按所涵盖的主题划分。他从 $$$i$$$ 类别中挑选了 $$$p^{k_i}$$$ 问题($$$p$$$ 是他最喜欢的数字)。他想在两周内解决它们(耐心条件对约翰尼来说太难了,所以为了简单起见,他只考虑简单的任务,可以在这样的时间内解决)。现在,我们未来的特级大师必须决定首先讨论哪些主题,第二周讨论哪些主题。帮助他以这样的方式分配主题,使工作量平衡。

正式地,给定 $$$n$$$ 个数字 $$$p^{k_i}$$$,男孩想要将它们分成两个不相交的集合,最小化每个集合中数字之和之间的绝对差。求最小绝对差。输出对 $$$10^{9}+7$$$ 取模的结果。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — 测试用例的数量。每个测试用例描述如下:

第一行包含两个整数 $$$n$$$ 和 $$$p$$$ $$$(1 \leq n, p \leq 10^6)$$$。第二行包含 $$$n$$$ 整数 $$$k_i$$$ $$$(0 \leq k_i \leq 10^6)$$$。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

输出一个整数——提醒将答案除以$$$1\,000\,000\,007$$$。

示例

输入 #1

4
5 2
2 3 4 4 3
3 1
2 10 1000
4 5
0 1 1 100
1 8
89

输出 #1

4
1
146981438
747093407

注意

你必须最小化差异,而不是余数。例如,如果最小差异等于 $$$2$$$,但也存在差异为 $$$10^9 + 8$$$ 的分布,则答案为 $$$2$$$,而不是 $$$1$$$。

在示例的第一个测试用例中,有以下数字:$$$4$$$、$$$8$$$、$$$16$$$、$$$16$$$ 和 $$$8$$$。我们可以将它们分为这样两个集合:$$${4, 8, 16}$$$ 和 $$${8, 16}$$$。那么集合中的数字之和之间的差将是 $$$4$$$。