F1. Выборы в Саранске (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное отличие в том, что $$$x = 1$$$

По пути домой после покупки своей любимой газировки «Zola Cero» Егор увидел, что в Саранске проходят выборы на пост «Лучшее число».

На избирательном участке находятся $$$n$$$ человек. Каждый человек принес с собой число $$$a_i$$$. Когда $$$i$$$-й человек заходит в кабинку для голосования, он выбирает кандидата, который является делителем числа $$$a_i$$$. Обозначим выбранного кандидата через $$$p_i$$$.

После того как все проголосовали, получился массив голосов $$$[p_1, p_2, \ldots, p_n]$$$.

Егор очень любит число $$$x$$$ и считает голосование идеальным, если $$$x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$$$$$^{\text{∗}}$$$ = $$$p_1 \cdot p_2 \cdot \ldots \cdot p_n$$$. Помогите ему найти количество различных$$$^{\text{†}}$$$ массивов $$$p$$$ по модулю $$$10^9 + 7$$$, которые являются идеальными.

$$$^{\text{∗}}$$$$$$lcm$$$ — наименьшее общее кратное.

$$$^{\text{†}}$$$Два массива голосов считаются различными, если существует индекс $$$i$$$, в котором два массива имеют отличные друг от друга элементы.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора записаны два целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$x = 1$$$) — число голосующих в избирательном участке и любимое число Егора.

Во второй строке каждого набора записаны $$$n$$$ целых чисел: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$) — числа, которые принесли с собой голосующие.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите количество способов по модулю $$$10^9 + 7$$$ проголосовать так, чтобы итоговый массив голосов удовлетворял условию.

Пример
Входные данные
4
4 1
2 3 1 4
2 1
2 4
6 1
3 9 1 6 4 5
7 1
1 2 3 67 13 8 8
Выходные данные
8
4
40
64