CF1361B.Johnny and Grandmaster

Johnny has just found the new, great tutorial: "How to become a grandmaster?". The tutorial tells many strange and unexpected for Johnny things, such as you have to be patient or that very important is solving many harder and harder problems.

The boy has found an online judge with tasks divided by topics they cover. He has picked $p^{k_i}$ problems from $i$-th category ($p$ is his favorite number). He wants to solve them in two weeks (the patience condition is too hard for Johnny, so for simplicity, he looks only at easy tasks, which can be solved in such a period). Now our future grandmaster has to decide which topics to cover first and which the second week. Help him assign topics in such a way, that workload is balanced.

Formally, given $n$ numbers $p^{k_i}$, the boy wants to divide them into two disjoint sets, minimizing the absolute difference between sums of numbers in each set. Find the minimal absolute difference. Output the result modulo $10^{9}+7$.

Johnny 刚刚发现了一篇全新的、非常棒的教程：“如何成为大师级选手？”。这篇教程向 Johnny 介绍了许多奇怪而意想不到的知识点，例如：你必须具备耐心，以及非常重要的一点是——持续求解难度不断递增的问题。

这位少年找到了一个在线评测系统，其中题目按其所涵盖的主题进行了分类。他从第 $i$ 个主题中挑选了 $p^{k_i}$ 道题（$p$ 是他最钟爱的数字）。他计划在两周内完成这些题目（由于“耐心”这一条件对 Johnny 来说过于困难，因此为简化问题，他只考虑那些能在该时间段内轻松解决的简单题目）。现在，这位未来的国际象棋大师需要决定：第一周学习哪些主题，第二周学习哪些主题。请帮助他将这些主题分配到两周中，使得两周的工作量尽可能均衡。

形式化地，给定 $n$ 个数 $p^{k_i}$，该少年希望将它们划分为两个互不相交的集合，使得这两个集合各自元素之和的绝对差值最小。请找出该最小绝对差值，并将结果对 $10^{9}+7$ 取模后输出。

Input consists of multiple test cases. The first line contains one integer $t$ $(1 \leq t \leq 10^5)$ — the number of test cases. Each test case is described as follows:

The first line contains two integers $n$ and $p$ $(1 \leq n, p \leq 10^6)$. The second line contains $n$ integers $k_i$ $(0 \leq k_i \leq 10^6)$.

The sum of $n$ over all test cases doesn't exceed $10^6$.

输入包含多个测试用例。第一行包含一个整数 $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$。

Output one integer — the reminder of division the answer by $1\,000\,000\,007$.

输出一个整数——答案对 $1\,000\,000\,007$ 取模的余数。

You have to minimize the difference, not it's remainder. For example, if the minimum difference is equal to $2$, but there is also a distribution where the difference is $10^9 + 8$, then the answer is $2$, not $1$.

In the first test case of the example, there're the following numbers: $4$, $8$, $16$, $16$, and $8$. We can divide them into such two sets: ${4, 8, 16}$ and ${8, 16}$. Then the difference between the sums of numbers in sets would be $4$.

你需要最小化差值本身，而不是它的余数。例如，若最小差值为 $2$，但还存在一种分配方式使得差值为 $10^9 + 8$，则答案是 $2$，而非 $1$。

在示例的第一个测试用例中，给定的数字为：$4$、$8$、$16$、$16$ 和 $8$。我们可以将它们划分为如下两个集合：$\{4, 8, 16\}$ 和 $\{8, 16\}$。此时，两集合元素之和的差值为 $4$。