B. Джонни и гроссмейстер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джонни недавно нашел новый отличный туториал: «Как стать гроссмейстером?». В туториале говорится много странных и неожиданных для Джонни вещей, таких как то, что он должен быть терпеливым или что очень важно решать много все более и более сложных задач.

Мальчик нашел онлайн архив с задачами, разделенными по темам. Он выбрал $$$p^{k_i}$$$ задач из $$$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$$$.

Пример
Входные данные
4
5 2
2 3 4 4 3
3 1
2 10 1000
4 5
0 1 1 100
1 8
89
Выходные данные
4
1
146981438
747093407
Примечание

Вы должны минимизировать модуль разности, а не остаток модуля разности. Например, если минимальная разность равна $$$2$$$, но существует также разбиение, при котором разность равна $$$10^9 + 8$$$, ответ равен $$$2$$$, а не $$$1$$$.

В первом наборе входных данных числа равны: $$$4$$$, $$$8$$$, $$$16$$$, $$$16$$$ и $$$8$$$. Мы можем разделить их на два набора: $$${4, 8, 16}$$$ и $$${8, 16}$$$. Тогда модуль разности между суммами чисел в наборах будет равен $$$4$$$.