CF1361B Johnny and Grandmaster

Johnny 刚刚发现了一篇新的、很棒的教程：“如何成为一名 grandmaster？”。这篇教程告诉了 Johnny 许多令他感到奇怪和意外的事情，比如你必须要有耐心，或者不断解决越来越难的问题非常重要。 Johnny 找到了一个按题目类型分类的在线评测系统。他从第 $i$ 类中选取了 $p^{k_i}$ 道题目（$p$ 是他最喜欢的数字）。他打算在两周内解决这些题目（耐心的要求对 Johnny 来说太难了，所以为了简单起见，他只考虑那些能在两周内解决的简单题目）。现在，这位未来的 grandmaster 需要决定第一周和第二周分别解决哪些类型的题目。请帮助他分配题目，使得两周的工作量尽可能均衡。 形式化地说，给定 $n$ 个数 $p^{k_i}$，Johnny 想要将它们分成两个不相交的集合，使得两个集合中数字和的绝对值差最小。请你求出这个最小的绝对值差。输出结果对 $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$ 取模后的结果。

你需要最小化的是差值本身，而不是其取模后的结果。例如，如果最小差值为 $2$，但存在一种分配方式使得差值为 $10^9 + 8$，那么答案应为 $2$，而不是 $1$。 在样例的第一个测试数据中，有如下数字：$4$、$8$、$16$、$16$ 和 $8$。我们可以将它们分成两个集合：$\{4, 8, 16\}$ 和 $\{8, 16\}$。这样两个集合中数字和的差为 $4$。 由 ChatGPT 4.1 翻译